0-1背包动态规划解决方案不起作用

Question

这是在极客上为极客找到的0-1背包问题动态编程代码。我已经为我自己的测试更改了输入，但它似乎不起作用。最优解不是第4项(v:10，w:7)的1和第1项(v:1，w:1)的3加起来是13吗？当我运行代码并手动执行算法时，结果是包含第2项和第4项的结果是12。我哪里错了？

// A Dynamic Programming based solution for 0-1 Knapsack problem
#include<stdio.h>

// A utility function that returns maximum of two integers
int max(int a, int b) { return (a > b)? a : b; }

// Returns the maximum value that can be put in a knapsack of capacity W
int knapSack(int W, int wt[], int val[], int n)
{
int i, w;
int K[n+1][W+1];

// Build table K[][] in bottom up manner
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];
}

int main()
{
    int val[] = {1, 2, 5, 10};
    int wt[] = {1, 3, 4, 7};
    int W = 10;
    int n = sizeof(val)/sizeof(val[0]);
    printf("%d", knapSack(W, wt, val, n));
    return 0;
}

Answer 1

因为该算法解决了0-1背包问题。

在这个公式中，每个项目只有一个实例可用。这就是为什么解决方案只使用一次项的原因。

(也许你在想每件东西都有无限制(或有限制)数量的背包)