c - 了解C中的背包解决方案

#include <stdio.h>
#include <conio.h>

void main() {
    int p[20], w[20], kn[20][20], x[20], i, j, n, weight;
    Clrscr();
    printf("\nEnter the value of n ");
    scanf("%d", &n);
    printf("\nEnter the price of the items ");
    for (i = 0; i < n; i++) {
        scanf("%d", &p[i]);
    }
    printf("\nEnter the weight of the items ");
    for (i = 0; i < n; i++) {
        scanf("%d", &w[i]);
    }
    printf("\nEnter the weight of the knapsack ");
    scanf("%d", &weight);
    printf("\nThe knapsack is ");
    for (i = 0; i <= n; i++) {
        printf("\n");
        for (j = 0; j <= weight; j++) {
            if (i == 0 || j == 0) {
                kn[i][j] = 0;
            } else
            if (w[i - 1] > j) {
                kn[i][j] = kn[i - 1][j];
            } else {
                kn[i][j] = (kn[i - 1][j] > (kn[i - 1][j - w[i - 1]] + p[i - 1])) ?
                            kn[i - 1][j] : (kn[i - 1][j - w[i - 1]] + p[i - 1]);
            }
            printf("%d ", kn[i][j]);
        }
    }
    printf("\n\nThe optimal solution is %d", kn[n][weight]);
    i = n;
    j = weight;
    while (i != 0) {
        if (kn[i][j] == kn[i - 1][j]) {
            x[i-1] = 0;
            i = i - 1;
        } else {
            x[i - 1] = 1;
            j = j - w[i - 1];
            i = i - 1;
        }
    }
    printf("\n\nThe 0/1 knapsack is ");
    for (i = 0; i < n; i++) {
        printf("\nX[%d]=%d", i + 1, x[i]);
    }
    getch();
}

嘿伙计们我是新来的，但我试过课本上的背包问题我真的不明白它是如何工作的，尤其是不明白这条线
kn[i][j]=(kn[i-1][j]>(kn[i-1][j-w[i-1]]+p[i-1]))?kn[i-1][j]:(kn[i-1][j-w[i-1]]+p[i-1]);
好吧，如果有人想解释请。。。
非常感谢：）

最佳答案

答案在于，你要么接受第条，要么不接受。
如果你拿了第项，那么问题就减少到用背包找到最优解。
如果你不接受第项，就跳过它所以解决方案是i。
为什么i？因为你没有带任何东西，所以你可以用同样的重量来装满背包。
现在你有了这两个选择，然后选择一个最大填充量的选项。这就是为什么你需要找到这两个最大值的原因。
这就是你用三元算符做的。
或者，你可以使用i-1函数来获得这两个函数的最大值。这也会得到同样的答案。
也可以使用ol'和simplej-w[i]。

if( kn[i-1][j]>(kn[i-1][j-w[i-1]]+p[i-1]))
  kn[i][j]=kn[i-1][j];
else
  kn[i][j]=(kn[i-1][j-w[i-1]]+p[i-1]);

这个三元运算符最终归结为这个i。
kn[i-1][j]基本上是我们正在考虑的权重我们也在设法解决重量较小的问题j表示这一点。它有助于给我们子问题的答案。

关于c - 了解C中的背包解决方案，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/45903157/