尝试理解经典的背包问题递归公式

Question

尝试理解经典的背包问题递归公式

javaalgorithmdynamic-programmingknapsack-problem

3

我正在阅读关于（无界）背包问题的文章，据我所知这是DP中的经典问题。虽然我认为我理解了它的解决方案，但我不清楚如何将其转换为实际代码。例如，在以下递归“公式”中： M(j) = MAX {M(j-1), MAX i = 1 to n (M(j - Si) + Vi) } for j >=1 我不确定如何将其转换为代码，因为我不清楚内部MAX是否应该存在，或者它应该被替代为： M(j) = MAX {M(j-1), M(j - Si) + Vi } for j >=1 请帮助我弄清楚这个公式并编写代码？

- Cratylus

说实话，只要你写出原因，我并不在意负评。 - Cratylus

你知道吗，我的一些帖子也是这样。没有提到任何理由就进行了负评。 - mamdouh alramadan

也许更适合在http://cstheory.stackexchange.com上发布？ - Waleed Khan

@WaleedKhan：我不知道SE的情况。 - Cratylus

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mamdouh alramadan · Accepted Answer

你可以像这样编写代码：

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

图片描述

这意味着以下内容：

它的意思是，Sk的最佳子集，其总重量为w是：

1）Sk-1中总重量> w的最佳子集或

2）Sk-1中总重量> w-wk加上项目k的最佳子集。

Sk的最佳子集，其总重量> w，可以包含项目k或不包含项目k。

第一种情况： wk>w。项目k不能成为解决方案的一部分，因为如果是，总重量将> w，这是不可接受的。

第二种情况：wk <= w。然后项k可以在解决方案中，并且我们选择具有更大价值的情况。