algorithm - 01 Knapsack 使用一维数组存储中间解

Question

我已经在线阅读了 01 背包问题的几个解决方案。当总权重为 W 时，他们每个人都试图存储从 0..i 和总权重 w 中选择的子问题权重的解决方案。所以基本上他们需要一个 2D 数组来存储子问题的解决方案。我的问题是为什么他们要解决一组权重的问题，从而增加另一个维度。我正在发布我的解决方案，它迭代所有可用的重量并建立解决方案直到背包的重量。这需要仅使用一维数组。我在这里错过了什么吗？我在下面粘贴我的代码。

public class KnapSack01 {

//The Weight Matrix
int[] weight;

//The Benefit Matrix
int[] benefit;

//The size of Knap-Sack
int M;

//array to store solutions to subproblem
//B[i] = optimal solution for capacity i
int[] B;

//Array to print out the chosen weights
String[] chosenWeight;

int calculate() {
    B = new int[M + 1];
    chosenWeight = new String[M + 1];
    for (int i = 0; i < B.length; i++) {
        B[i] = 0;
        chosenWeight[i] = "";
    }
    for (int w = 1; w <= M; w++) {
        for (int i = 0; i < weight.length; i++) {
            int b1 = benefit[i];
            int remaining = w - weight[i];
            int temp = B[w];
            if (remaining >= 0) {
                temp = b1 + B[remaining];
            }
            if (temp >= B[w]) {
                B[w] = temp;
                chosenWeight[w] = chosenWeight[w] + "," + weight[i];
            }
        }
    }
    System.out.println(chosenWeight[M].substring(1,
        chosenWeight[M].length()));
    return B[M];
}

/**
 * @param args
 */
public static void main(String[] args) {
    int[] w = { 2, 3, 4, 5 };
    int[] b = { 3, 4, 5, 6 };
    int capacity = 5;

    KnapSack01 ks = new KnapSack01();
    ks.weight = w;
    ks.benefit = b;
    ks.M = capacity;
    System.out.println(ks.calculate());
}

Answer 1

您的代码不正确，因为您可以选择相同的项目两次(或更多次)。
这是一个例子:

w = {1, 1}  
b = {2, 1}
capacity = 2

正确答案是 3，但您的代码返回 4(它两次选择第一项)。

这个算法其实可以用一维数组来实现，但是需要不同的循环顺序:
外层循环应遍历项目，内层循环应遍历从 W 到 0 的权重。