编辑代码

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 (object item : objectsStolen) {
                maxvalue = maxvalue + item.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 (Main.object object : objectsStolen) {
                maxvalue = maxvalue + object.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;
                    return Double.compare(rightprice, leftprice);
                }
            });
            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.print("背包的物品如下：");
            for (object item : objectsStolen1) {
                maxValue += item.value;
                System.out.print(item.name + '\t');
            }
            System.out.println("\n" + "总价值：" + maxValue);
            System.out.println("------------------------------");
        }
        
        public void test2() {
            object[] objects1 =
                    {
                            new object("IPhone", 2000, 1),
                            new object("吉他", 1500, 1),
                            new object("笔记本电脑", 8000, 3),
                            new object("音箱", 1500, 3),
                            new object("华为笔记本", 15000, 5)
                    };
            
            int[] path1 = {0, 0, 0, 0};
            int maxvalue = 0;
            LinkedList<object> objectsStolen1 = solve(5, objects1);
            System.out.print("背包的物品如下：");
            for (object item : objectsStolen1) {
                maxvalue += item.value;
                System.out.print(item.name + '\t');
                
            }
            System.out.println("\n" + "总价值：" + maxvalue);
            System.out.println("------------------------------");
    
        }
        
        public void test3() {
            object[] objects1 =
                    {
                            new object("IPhone", 2000, 1),
                            new object("吉他", 1500, 1),
                            new object("笔记本电脑", 8000, 3),
                        
                    };
            
            int[] path1 = {0, 0, 0, 0};
            int maxvalue = 0;
            LinkedList<object> objectsStolen1 = solve(5, objects1);
            System.out.print("背包的物品如下：");
            for (object item : objectsStolen1) {
                maxvalue += item.value;
                System.out.print(item.name + '\t');
            }
            System.out.println("\n" + "总价值为：" + maxvalue);
            System.out.println("------------------------------");
    
        }
    }
}