dynamic - 背包最大利润

Question

有 4 种物品：A 重量 2LB 利润 40 美元，B 重量 5LB 利润 30 美元，C 重量 10LB 利润 50 美元，D 重量 5LB 利润 10 美元。计算你可以从 4 件背包重量为 16 磅的物品中获得的最大总利润。你不能拿一个项目的任何部分，只能拿整个。

请说明如何使用背包问题方法解决上述问题。

Answer 1

一个简单的解决方案是考虑项目的所有子集并计算所有子集的总权重和价值。然后你应该考虑只取重量小于或等于你的背包容量的子集。从所有这些子集中，选择最大值子集。

要考虑项目的所有子集，每个项目可以有两种情况：

• 该项目包含在最佳子集中，
• 该项目不包含在最佳子集中。

假设您的背包容量为W。因此，可以从n个项目中获得的最大值是以下两个值中的最大值。

1. n-1项和W权重得到的最大值（不包括第n项）
2. 第n项的值加上n-1项得到的最大值， W减去第n项（包括第n项）的权重。

如果第 n 项的权重大于W，则不能包含第 n 项，并且案例 1 是唯一的选择。这将是一种幼稚的方法，解决方案将花费2 ⁿ时间。

现在对于重叠子问题：

weight = {2, 5, 10, 5}
Capacity = 16
The recursion tree would look like:       
// Here n,k -> items remaining, capacity remaining
// Going to left child -> including the item at hand
// Going to right child -> excluding the item at hand
                       _______4,16______    
                      /                 \   
                     /                   \
                  3,14                     3,16
                 /    \                    /   \
                /      \                  /     \
             2,9        2,14             2,5     2,16
              \          / \             \         / \
               \        /   \             \       /   \__
               1,9   1,4   1,14          1,5     1,6     1,16
              /\            /\          /\       /\        /  \
             /  \          /  \        /  \     /  \      /    \
           0,4  0,9      0,9  0,14    0,0 0,0  0,1  0,6   0,11   0,16

由于叶子中有重叠的子问题，我们可以使用动态规划来解决它。如果您存储这些值，那么以后使用它们会很有效。这里匹配发生在叶节点中，如果你举其他例子，你会看到匹配可能发生在叶节点之前很远的地方。

伪代码如下所示：

Procedure Knapsack(n, W):    //here, n = number of items, W = capacity of Knapsack
for i from 0 up to n
    for j from 0 up to W
        if i == 0 or j == 0
            table[i][j] :=0
        else if weight[i-1] <= j
            table[i][j] := max(profit[i-1] + table[i-1][w-weight[i-1]], table[i-1][j])
        else
            table[i][j] := table[i-1][j]
        end if
    end for
end for
Return table[n][W]