java - 在 0/1 KnapSack 中打印结果(递归蛮力)

Question

public static int KnapSack(int capacity, Item[] items, int numItems) {
    if (numItems == 0 || capacity == 0)
        return 0;
    if (items[numItems-1].weight > capacity)
        return KnapSack(capacity, items, numItems-1);
    else {
        int took = items[numItems-1].value + KnapSack(capacity - items[numItems-1].weight, items, numItems-1);
        int left = KnapSack(capacity, items, numItems-1);
        return Math.max(took, left);
    }     
}  

所以我有一个有效的 0/1 递归蛮力算法来解决 KnapSack 问题。我想知道打印出工作解决方案的方法是什么(即从项目集中收集到背包中的项目)。我已经尝试了很多事情，例如添加到列表中并尝试跟踪我添加的内容，但都没有解决实现或设计问题。所以我来这里寻求帮助，谢谢!

Answer 1

要跟踪拿走的元素，请尝试以下方法:

public static int KnapSack(int capacity, Item[] items, int numItems, ArrayList<Integer> taken) {
    if (numItems == 0 || capacity == 0)
        return 0;
    if (items[numItems-1].weight > capacity)
        return KnapSack(capacity, items, numItems-1, taken);
    else {
        final int preTookSize = taken.size();
        final int took = items[numItems-1].value + KnapSack(capacity - items[numItems-1].weight, items, numItems-1, taken);

        final int preLeftSize = taken.size();
        final int left = KnapSack(capacity, items, numItems-1, taken);

        if (took > left) {
            if (taken.size() > preLeftSize)
                taken.removeRange(preLeftSize, taken.size());
            taken.add(Integer.valueOf(numItems - 1));
            return took;
        }
        else {
            if (preLeftSize > preTookSize)
                taken.removeRange(preTookSize, preLeftSize);
            return left;
        }
    }     
}

这可能不是最有效的，但我认为它应该有效。

(为了提高效率，您可以尝试将获取的 ArrayList 预先分配为“足够大”，以便在递归循环期间不需要进行任何分配。)