试图找出经典的背包复发 [英] Trying to figure out the classic Knapsack recurrence

问题描述

我读关于背包问题（无限），这是，据我了解在DP上的经典之作。
虽然我觉得我理解的解决方案，因为我读了它，我不明白我怎么可以把它转化为实际的code。
例如在下面的复发配方：

M（j）条= MAX {M（J-1），MAX I = 1到n（M（j - 硅）+六）}为J＆GT; = 1

我不知道我怎么可以把此code，因为它是我不清楚，如果内部 MAX 应该存在，或者它应该只是而不是：
M（j）条= MAX {M（J-1），M（的J - 硅）+六}为J＆GT; = 1

任何帮助找出公式和code呢？

解决方案

您可以code这样的：

 为W = 0至W // W是最大容量
V [0，瓦特] = 0
对于i = 1到n
v [电流，0] = 0
对于i = 1到n
为瓦特= 0至W
    如果无线＆LT; = W //项目，我可以成为解决方案的一部分，
        如果双+ V [I-1，瓦特-WI]≥ v [电流-1，瓦特]
            v [电流，瓦特] =双+ V [I-1，W-无线]
        其他
            v [电流，瓦特] = V [I-1，瓦特]
    否则v [电流，瓦特] = V [I-1，瓦特] //无线＆GT; W¯¯
 

这意味着：

这意味着，的SK，有总重量W最好的子集：

1）的最佳子集SK-1具有总重量> w或

2）的最佳子集SK-1，有总重> W-WK加项氏/ P>

Sk的的具有总重量>瓦特，或者最好子集包含项k或不

第一种情况：周>瓦特项ķ不能成为解决方案的一部分，因为如果是，总重量是>瓦特，这是不可接受的。

案例二：周＆LT; =瓦特然后这一项目。K可在该溶液中，我们选择具有较大值的情况。

I am reading about the Knapsack Problem (unbounded) which is, as I understand a classic in DP.
Although I think I understand the solution as I read it, I am not clear how I can translate it to actual code.
For example in the following recurrence "formula":

M(j) = MAX {M(j-1), MAX i = 1 to n (M(j - Si) + Vi) } for j >=1

I am not sure how I can translate this to code, since it is not clear to me if the inner MAX should be there or it should just be instead:
M(j) = MAX {M(j-1), M(j - Si) + Vi } for j >=1

Any help to figure out the formula and to code it?

解决方案

you can code it like this:

for w = 0 to W   //W is the maximum capacity
V[0,w] = 0
for i = 1 to n
V[i,0] = 0
for i = 1 to n
for w = 0 to W
    if wi <= w // item i can be part of the solution
        if  bi + V[i-1,w-wi] > V[i-1,w]
            V[i,w] = bi + V[i-1,w- wi]
        else
            V[i,w] = V[i-1,w]
    else V[i,w] = V[i-1,w]  // wi > w 

this means the following:

It means, that the best subset of Sk that has total weight w is:

1) the best subset of Sk-1 that has total weight > w, or

2) the best subset of Sk-1 that has total weight > w-wk plus the item k

The best subset of Sk that has the total weight > w, either contains item k or not.

First case: wk>w. Item k can’t be part of the solution, since if it was, the total weight would be > w, which is unacceptable.

Second case: wk <= w. Then the item k can be in the solution, and we choose the case with greater value.

这篇关于试图找出经典的背包复发的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！