有N件物品和一个最大分量为W的背包，每件物品分量weight[i]，价值是value[i]。每件物品只能取一次，背包能保留的最大价值是多少？
动静布局五部曲：
a) 确定dp数组以及下标的含意
b) 确定递推公式
c) dp数组的初始化
d) 确定遍历程序
e) 举例推导dp数组
解题思路：
1) 确定dp数组以及下标的含意
dp[i][j]的定义为：从0~i的物品中任意取，背包容量为j的状况下价值总和最大是dp[i][j]
2) 递推公式
dp[i][j]从逻辑剖析上来看，有两个起源：即不放入物品i，那么dp[i][j] = dp[i-1][j]（表明在j容量下，物品i所占分量对应的价值小于0~i-1物品中选取的其余价值）。放入物品i，dp[i][j] = value[i] + dp[i-1][j-weight[i]]
最终得出dp[i][j]取上述两种起源的最大值。
公式：dp[i][j] = Max(dp[i-1][j], value[i] + dp[i-1][j-weight[i]])
3) dp数组初始化
依据dp数组的定义，背包容量为0时，最大价值永远为0。dp[i][0] = 0
依据递推公式可知，i取决于i-1，所以要对i=0时的状态做初始化。也就是只寄存物品0时，各个背包容量下的最大价值dp[0][j]
编码：
第一层循环物品，第二层循环背包容量
public static int packageOneOrZero(int[] weights, int[] values, int packageWeight) { // 定义dp[i][j]示意 从0~i的物品中任意放入容量为j的背包，最大价值总和为dp[i][j] int[][] dp = new int[values.length][packageWeight + 1]; // dp[0][j]初始化 for (int j = packageWeight; j >= weights[0]; j--) { dp[0][j] = dp[0][j - weights[0]] + values[0]; } for (int i = 1; i < values.length; i++) { for (int j = 0; j <= packageWeight; j++) { if (j < weights[i]) { dp[i][j] = dp[i - 1][j]; } else { dp[i][j] = Math.max(dp[i - 1][j - weights[i]] + values[i], dp[i - 1][j]); } } } return dp[values.length - 1][packageWeight]; } public static void main(String[] args) { int[] weights = new int[] {1, 3, 4}; int[] values = new int[] {15, 20, 30}; System.out.println(packageOneOrZero(weights, values, 4));}简化思路：将i-1和i进行合并，即应用一维数组进行运算
从新定义dp数组： dp[j]示意容量为j的背包，能够背的最大价值和为dp[j]
递推公式： dp[j] = Max(dp[j], dp[j – weight[i]] + value[i])，实现了dp[j]的复用
递推方向：为保障不反复取用物品，所以对于背包容量j的循环是倒序的
编码：
class Solution { public static int packageOneOrZero(int[] weights, int[] values, int packageWeight) { int[] dp = new int[packageWeight + 1]; for (int i = 0; i < weights.length; i++) { for (int j = packageWeight; j >= weights[i]; j--) { dp[j] = Math.max(dp[j - weights[i]] + values[i], dp[j]); } } return dp[packageWeight]; } public static void main(String[] args) { int[] weights = new int[] {1, 3, 4}; int[] values = new int[] {15, 20, 30}; System.out.println(packageOneOrZero(weights, values, 4)); }}