编辑代码

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;

public class Backpack {
    public static void stealObjects(int packCapacity, Item[] items, int curItemIndex, int[] path, LinkedList<Item> objectsStolen) {

        if (curItemIndex == items.length) {
            objectsStolen.clear();
            for (int index = 0; index < path.length; ++index) {
                if (path[index] > 0) {
                    objectsStolen.add(items[index]);
                }
            }
            return;
        }

        // 当前的最佳解
        int maxValue = 0;
        for (int i = 0; i < objectsStolen.size(); ++i) {
            maxValue += objectsStolen.get(i).value;
        }

        //当前已选的价值和重量
        int curValue = 0;
        int curWeight = 0;
        for (int i = 0; i < curItemIndex; ++i) {
            if (path[i] > 0) {
                curValue += items[i].value;
                curWeight += items[i].weight;
            }
        }

        //放入当前物体
        //保证物体是能够放入，方案是可行的
        if (items[curItemIndex].weight <= packCapacity - curWeight) {

            path[curItemIndex] = 1;

            //当前节点的边界值
            int upperValue = 0;
            upperValue = curValue + items[curItemIndex].value;
            if (curItemIndex < items.length - 1) {
                Item nextItem = items[curItemIndex + 1];
                upperValue += (packCapacity - curWeight - items[curItemIndex].weight) * (nextItem.value/nextItem.weight);
            }


            //边界值能超越当前最佳解
            if (upperValue > maxValue) {
                stealObjects(packCapacity, items, curItemIndex + 1, path, objectsStolen);
            }

        }

        //不放入当前物体
        path[curItemIndex] = 0;

        //当前最佳解
        maxValue = 0;
        for (int i = 0; i < objectsStolen.size(); ++i) {
            maxValue += objectsStolen.get(i).value;
        }

        //当前节点的边界值
        int upperValue = curValue;
        if (curItemIndex < items.length - 1) {
            Item nextItem = items[curItemIndex + 1];
            upperValue += (packCapacity - curWeight) * (nextItem.value/nextItem.weight);
        }

        //边界值能超越当前最佳解
        if (upperValue > maxValue) {
            stealObjects(packCapacity, items, curItemIndex + 1, path, objectsStolen);
        }

    }

    public static LinkedList<Item> solveBackpackProblem(int packCapacity, Item[] items) {
        LinkedList<Item> objectsStolen = new LinkedList<Item>();
        int[] path = new int[items.length];

        //按照单价从高到低进行排序
        Arrays.sort(items, new Comparator<Item>() {
            public int compare(Item left, Item right) {
                double leftUnitPrice =(double) left.value/left.weight;
                double rightUnitPrice =(double) right.value/right.weight;
                if (leftUnitPrice > rightUnitPrice){
                    return -1;
                }
                else if (leftUnitPrice == rightUnitPrice) {
                    return 0;
                }
                else {
                    return 1;
                }
            }
        });

        stealObjects(packCapacity, items, 0, path, objectsStolen);
        return objectsStolen;
    }

    public static void test() {
        Item[] items = {
                new Item("IPhone", 2000, 1),
                new Item("吉他", 1500, 1),
                new Item("笔记本电脑", 2000, 3),
                new Item("音箱", 3000, 4)
        };

        int[] path = {0, 0, 0, 0};


        int maxValue = 0;
        LinkedList<Item> objectsStolen = solveBackpackProblem(4, items);



        System.out.println("偷了如下物品：");
        for (Item item : objectsStolen) {
            maxValue += item.value;
            System.out.println(item.name);
        }

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

    }

    public static void main(String[] args) {
        Backpack.test();
    }
}

class Item {
    public String name;
    public int value;
    public int weight;

    public Item(String n, int v, int w) {
        this.name = n;
        this.value = v;
        this.weight = w;
    }
}

class GreedyItem {
    public String name;
    public double totalWeight;
    public double totalValue;

    public GreedyItem(String itemName, double weight, double value) {
        this.name = itemName;
        this.totalWeight = weight;
        this.totalValue = value;
    }

    public GreedyItem(GreedyItem item) {
        this.name = item.name;
        this.totalWeight = item.totalWeight;
        this.totalValue = item.totalValue;
    }
}