algorithm - 0-1 背包动态规划解法行不通

Question

这是在geeks for geeks上找到的0-1背包问题动态规划代码。我已经为自己的测试更改了输入，但它似乎不起作用。最优解不是第 4 项中的 1 (v:10, w:7) 和第 1 项中的 3 (v:1, w:1) 加起来等于 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背包问题。

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

(也许您正在考虑每件元素的数量不受限制(或限制)的背包)