这些是2背包算法一样吗？ （他们总是输出同样的事情） [英] Are these 2 knapsack algorithms the same? (Do they always output the same thing)

问题描述

在我的code，假设C的容量，N是项目的数量，W [j]为类j和v [D]的重量为项目j的值，它能做的同样的事情0-1背包算法？我一直在试图对某些数据集我的code，它似乎是这样。我不知道这样做的原因是因为0-1背包算法，我们一直被教导是2维的，而这是一维的：

 的（INT J = 0; J＆LT; N; J ++）{
    如果（C-W [J]℃的）继续;
    的for（int i = Cw的研究[J]; I＆GT; = 0; --i）{//循环向后prevent重复计算
        DP [I + W [J]] = MAX（DP [I + W [J]]，DP [I] + V [J]）; //循环FWD是无界的问题
    }
}
的printf（不重复计算最大值（循环向后）％D \ N，DP [C]）;
 

下面是我实现0-1背包算法：（具有相同的变量）

 的for（int i = 0; I＆n种;我++）{
    对于（INT J = 0; J＆LT; = C; J ++）{
        如果（的J  -  W [1]  -  0）DP2 [I] [J]。= I == 0 0：DP2 [I-1] [J]。？
        别的DP2 [I] [j]的最大值=（ⅰ== 0？0：DP2 [I-1] [j]时，DP2 [I-1] [JW [I] + V [I]）;
    }
}
的printf（0-1背包数：％d \ N，DP2 [N-1] [C]）;
 

解决方案

是的，你的算法让你相同的结果。这增强了经典0-1背包是相当流行：维基百科它解释为如下：

  

此外，如果我们只使用一维数组M [W]保存当前的最优值，并通过在这个阵列I + 1次，从M [W]改写为米[1]每一次，我们得到相同的结果只有O（W）的空间。

请注意，他们特别提到您的落后循环。

In my code, assuming C is the capacity, N is the amount of items, w[j] is the weight of item j, and v[j] is the value of item j, does it do the same thing as the 0-1 knapsack algorithm? I've been trying my code on some data sets, and it seems to be the case. The reason I'm wondering this is because the 0-1 knapsack algorithm we've been taught is 2-dimensional, whereas this is 1-dimensional:

for (int j = 0; j < N; j++) {
    if (C-w[j] < 0) continue;
    for (int i = C-w[j]; i >= 0; --i) { //loop backwards to prevent double counting
        dp[i + w[j]] = max(dp[i + w[j]], dp[i] + v[j]); //looping fwd is for the unbounded problem
    }
}
printf( "max value without double counting (loop backwards) %d\n", dp[C]);

Here is my implementation of the 0-1 knapsack algorithm: (with the same variables)

for (int i = 0; i < N; i++) {
    for (int j = 0; j <= C; j++) {
        if (j - w[i] < 0) dp2[i][j] = i==0?0:dp2[i-1][j];
        else dp2[i][j] = max(i==0?0:dp2[i-1][j], dp2[i-1][j-w[i]] + v[i]);
    }
}
printf("0-1 knapsack: %d\n", dp2[N-1][C]);

解决方案

Yes, your algorithm gets you the same result. This enhancement to the classic 0-1 Knapsack is reasonably popular: Wikipedia explains it as follows:

Additionally, if we use only a 1-dimensional array m[w] to store the current optimal values and pass over this array i + 1 times, rewriting from m[W] to m[1] every time, we get the same result for only O(W) space.

Note that they specifically mention your backward loop.

这篇关于这些是2背包算法一样吗？ （他们总是输出同样的事情）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！