Dynamic Programming -- Knapsack

这是一道经典的dp问题。

问题描述：有一些货物，他们有自己的重量和价值，一艘船有最大载重量，要求给定货物和船的载重量的情况下，可以获得的最大的价值

items [{1:1}, {2,4}, {3,5}]  weight = 5

下面用这个表格的填写来说明思路，将表格命名为dp：

	0	1	2	3	4	5
{1}	0	1	1	1	1	1
{1, 2}	0
{1, 2, 3}

列标题表示的是最大重量，行标题是此时可以装的货物；

需要填入的是当前最大的价值。按行依次填写。

第一行：

W = 0: 什么也不能装，val = 0

W = 1: 1 >= 1, 可以装一个1

……

第二行：

W = 0: val = 0

W = 1: 1 < 2, 不能装入新增加的2， $val = dp[0][1] = 1$

W = 2: 2 >=2, 可以装入新增加的2，但是要考虑是否装入，如果装入，剩余的重量是0，要从前一行中找到重量为0时最大的val，也可以选择不装，val就和前一行的相同。 $dp[1][2] = Math.max(dp[0][2], 2 + dp[0][2-2])$

……

我们可以总结出如下计算公式：

if W < item.weight:  dp[i][W] = dp[i-1][W]
if W >= item.weight: dp[i][W] = Math.max(dp[i-1][W], item.val + dp[i-1][W-item.weight])

根据上面的公式，代码如下：

public int knapsack(Item[] items, int W) {
    int[][] dp = new int[items.length][W+1];
    for ( i = 0; i < items.length; i++) {
        for (int j = 1; j <= W; i++) {
            if (i == 0) {
                if (j >= items[i].weight) {
                    dp[i][j] = items[i].val;
                }
            } else {
                if (j >= items[i].weight) {
                    dp[i][j] = Math.max(dp[i-1][j], items[i].val + dp[i-1][j-items[i].val]);
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }  
        }
    }
    return dp[items.length-1][W];
}

和之前的coin change 2 一样，也可以吧dp简化为一个不断更新数值的数组：

public int knapsack(Item[] items, int W) {
    int[] dp = new int[W+1];
    for (Item item: items) {
        for (int i = 1; i <= W; i++) {
            if (i >= item.weight) {
                dp[i] = Math.max(dp[i], item.val + dp[i-item.weight]);
            }
        }
    }
    return dp[W];
}

Dynamic Programming -- Knapsack

推荐阅读更多精彩内容