这是一道经典的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，
W = 2: 2 >=2, 可以装入新增加的2，但是要考虑是否装入，如果装入，剩余的重量是0，要从前一行中找到重量为0时最大的val，也可以选择不装，val就和前一行的相同。
……
我们可以总结出如下计算公式：
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];
}
