编辑代码

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
public class Main {
    public static void main(String[] args) {
      Backpack backpack=new Backpack();
      backpack.test1();
      backpack.test2();
backpack.test3();
    }
     static class object {
        public String name;
        public int value;
        public int weight;

        public object(String name, int value, int weight) {
            this.name = name;
            this.value = value;
            this.weight = weight;
        }
    }
    static class Backpack {
        public  void steal(int pack, object[] objects, int curIndex, int[] path, LinkedList<object> objectsStolen) {

            if (curIndex == objects.length) {
                objectsStolen.clear();
                for (int i = 0; i < path.length; i++) {
                    if (path[i] > 0) {
                        objectsStolen.add(objects[i]);
                    }
                }
                return;
            }
            int maxvalue = 0;
            for (int i = 0; i < objectsStolen.size(); i++) {
                maxvalue =maxvalue+ objectsStolen.get(i).value;
            }
            int value = 0;
            int weight = 0;
            for (int i = 0; i < curIndex; i++) {
                if (path[i] > 0) {
                    value += objects[i].value;
                    weight += objects[i].weight;
                }
            }
            if (objects[curIndex].weight <= pack - weight) {
                path[curIndex] = 1;
                int upvalue = 0;
                upvalue = value + objects[curIndex].value;
                if (curIndex < objects.length - 1)
                {
                    object nextItem = objects[curIndex + 1];
                    upvalue += (pack - weight - objects[curIndex].weight) * (nextItem.value/nextItem.weight);
                }
                if (upvalue > maxvalue) {
                    steal(pack, objects, curIndex + 1, path, objectsStolen);
                }

            }
            path[curIndex] = 0;
            maxvalue = 0;
            for (int i = 0; i < objectsStolen.size(); i++)
            {
                maxvalue =maxvalue+ objectsStolen.get(i).value;
            }
            int upperValue = value;
            if (curIndex < objects.length - 1)
            {
                object nextItem = objects[curIndex + 1];
                upperValue += (pack - weight) * (nextItem.value/nextItem.weight);
            }
            if (upperValue > maxvalue)
            {
                steal(pack, objects, curIndex + 1, path, objectsStolen);
            }

        }

        public  LinkedList<object> solve(int pack, object[] objects)
        {
            LinkedList<object> objectsStolen = new LinkedList<object>();
            int[] path = new int[objects.length];
            Arrays.sort(objects, new Comparator<object>()
            {
                public int compare(object left, object right) {
                    double leftprice =(double) left.value/left.weight;
                    double rightprice =(double) right.value/right.weight;
                    if (leftprice > rightprice){
                        return -1;
                    }
                    else if (leftprice == rightprice) {
                        return 0;
                    }
                    else {
                        return 1;
                    }
                }
            });
            steal(pack, objects, 0, path, objectsStolen);
            return objectsStolen;
        }

        public  void test1() {
            
            object[] objects1 =
                    {
                    new object("IPhone", 2000, 1),
                    new object("吉他", 1500, 1),
                    new object("笔记本电脑", 2000, 3),
                    new object("音箱", 3000, 4)
            };
            int[] path1 = {0, 0, 0, 0};
            int maxValue = 0;
            LinkedList<object> objectsStolen1 = solve(4, objects1);
            System.out.println("测试用例一：偷的物品如下：");
            for (object item : objectsStolen1) {
                maxValue += item.value;
                System.out.println(item.name);
            }

            System.out.println("总价值：" + maxValue);

        }
        public  void test2() {
            object[] objects1 =
                    {
                            new object("IPhone", 2000, 1),
                            new object("吉他", 1500, 1),
                            new object("笔记本电脑", 2000, 3),
                            new object("音箱", 3000, 3),
                            new object("华为笔记本", 10000, 5)
                    };

            int[] path1 = {0, 0, 0, 0};
            int maxvalue = 0;
            LinkedList<object> objectsStolen1 = solve(5, objects1);
            System.out.println("测试用例二：偷的物品如下：");
            for (object item : objectsStolen1) {
                maxvalue += item.value;
                System.out.println(item.name);
            }

            System.out.println("总价值：" + maxvalue);

        }
        public  void test3() {
            object[] objects1 =
                    {
                            new object("IPhone", 2000, 1),
                            new object("吉他", 1500, 1),
                            new object("笔记本电脑", 2000, 3),

                    };

            int[] path1 = {0, 0, 0, 0};
            int maxvalue = 0;
            LinkedList<object> objectsStolen1 = solve(5, objects1);
            System.out.println("测试用例三：偷的物品如下：");
            for (object item : objectsStolen1) {
                maxvalue += item.value;
                System.out.println(item.name);
            }

            System.out.println("总价值：" + maxvalue);

        }
    }
}