如何实现背包算法，其中数组的索引表示项的权重

Question

我正在尝试实现一个算法来解决Knapsack problem

cst = 1;

for (j = 0; j < 200; j++) {
    if (kk - cst < 0) {
        continue;
        cst++;
    }

    for (i = kk - cst; i >= 0; --i) {
        C[i + cst] = max(C[i + cst], C[i] + index[cst]);
    }
    cst++;
}

index数组具有由数组的索引表示的各个项的值。我想知道我哪里错了。

Answer 1

在代码中

if(kk-cst < 0)
        {
            continue;
            cst++;
        }

是错误的。cst++将永远不会被执行。请检查并相应地更改您的逻辑。

Answer 2

在这里，cst的增量是不可达的代码。调换这两行

if (kk - cst < 0) {
    cst++;
    continue;
}

一个简单的动态编程背包实现是

int KnapSack(int W, int wt[], int val[], int n) {
   int i, w;
   int K[n + 1][W + 1];
   for (i = 0; i <= n; i++) {
       for (w = 0; w <= W; w++) {
           if (i == 0 || w == 0) K[i][w] = 0;
           else if (wt[i - 1] <= w)
                 K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
           else K[i][w] = K[i - 1][w];
       }
   }
   return K[n][W];
}

如http://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem/中所列