在二维动态规划中，01背包问题是动态规划中的经典问题。
如果遇到别的题目时，能够清楚地判断出它是一个01背包的类似问题，就可以套用01背包问题的模板，来进行解题。例如416. 分割等和子集 - 力扣（Leetcode）
本文内容即：
(1)01背包是什么
(2)如何用01背包思想解答其他题目（416. 分割等和子集 - 力扣（Leetcode））
有共n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
| 物品编号 | 重量 | 价值 |
|---|---|---|
| 物品0 | 1 | 15 |
| 物品1 | 3 | 20 |
| 物品2 | 4 | 30 |
解释：就是在有限的最大重量w里，选任意个具有重量和价值的商品（每个商品就1个），求能得到的最大价值。
对于动态规划类型的题目，我们知道：
- 需要将大问题拆解为多个小问题来解决
- 通过求出所有小问题的答案，放入dp数组，递推到大问题。
这个题目作为二维动态规划，是因为有2个动态变化的变量：最大背包重量，和，到底从前几？个物品里选。
（至于为什么要这么思考，不需要知道，因为我们要学习01背包的模式，来套其他的题目，因此这就是一个模板）
因此，可以构建二维dp数组dp[i][j] ：
表示从下标为[0-i]的物品里任意取，放进重量为j的背包，价值总和最大的值。
要求二维dp[i][j]的递推公式，其实就是求出dp所有子问题组成全集的方法：
思路是：先看能不能、再看要不要。
对于任意 dp[i][j]，其意义是最大重量为j的约束下，从0~i这些商品任选，能够得到的最大价值。动态规划的奥秘在于，不要去思考具体是怎么选、怎么组合得到的最大价值，而是仅仅通过“递推”的思想完成整个任务。
对于dp[i][j]而言，是从0~i里来选的，那么0~i里来选，有可能选了第i个，也有可能没选。
我们首先要考虑：能不能选第i个？
如果第i个的重量weight[i]比整个背包的最大承重j都要大，那么就算从0~i里选，实际上也肯定不能选第i个。因此，dp[i][j]其实等效于从0~i-1里选，最大容量为j的这个状态。
即：dp[i][j] = dp[i-1][j]
其次，我们要考虑：能选，但是要不要选？
如果现在能选第i个商品了，即第i个商品有资格被选（重量小于等于总重），就要考虑要不要选：
如果不要选上第i个，就仍然是等效于从0~i-1里选，最大容量为j。dp[i][j] = dp[i-1][j]
如果要选上第i个，那么dp[i][j]这个最大价值该等于什么呢？既然选了第i个，至少就有第i个的价值Value[i]，然后背包的最大容量只剩下j-weight[i]了，然后从0~i-1里接着选。
因此，为dp[i - 1][j - weight[i]] + value[i]
而dp[i][j]为最大价值，因此要取两种情况的Max。
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
初始化数组要考虑数组的意义。
首先，在j为0这一列，最大重量都为0了，你怎么组合也甭想装进去啊。因此dp[i][0]全为0
其次，i为0这一行 ，相当于从0~0的物品里任选（其实就是只选物品0），背包重量为j的约束下，能取得的最大价值。因为物品就1个，只能用一次，因此，在j>=weight[i]的列，都应该为Value[i].
package LeetcodeLearn.Algorithm.sort;
import java.util.Arrays;
/**
* @Author ZhangQihao
*/
public class package0_1 {
public static void main(String[] args) {
int[] weight = {1,3,4};
int[] value = {15,20,30};
int bagSize = 4;
testWeightBagProblem(weight,value,bagSize);
}
/**
* 动态规划获得结果
* @param weight 物品的重量
* @param value 物品的价值
* @param bagSize 背包的容量
*/
public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){
// 创建dp数组
int goods = weight.length; // 获取物品的数量
int[][] dp = new int[goods][bagSize + 1];
// 初始化dp数组
// 创建数组后，其中默认的值就是0
for (int j = weight[0]; j <= bagSize; j++) {
dp[0][j] = value[0];
}
// 填充dp数组:i是物品标号
// j是：容量为j的背包
for (int i = 1; i < weight.length; i++) {
for (int j = 1; j <= bagSize; j++) {
//能不能？
if (j < weight[i]) {
dp[i][j] = dp[i-1][j];
} else {
//能，但是要不要？
dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]);
//前为不要，后为要。
}
}
}
// 打印dp数组
for (int i = 0; i < goods; i++) {
for (int j = 0; j <= bagSize; j++) {
System.out.print(dp[i][j] + "\t");
}
System.out.println("\n");
}
}
}如何把01背包问题套用到其他问题上，以416. 分割等和子集 - 力扣（Leetcode）为例子进行说明。
题目：给你一个 只包含正整数 的 非空 数组
nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例：输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
能否分成两个等和数组，其实可以变换为：选任意多个数字的和，为所有数字总和 / 2。
如果像下面这样考虑，这个问题就类似01背包问题了。
相当于：坐标是商品标号，数值是商品的重量，要往一个背包里装，背包的最大重量为所有数值和/2。
即：从下标0~i选取其中任意的数字，是否存在一种方案，使其和为j
即：推出每一个状态，直到i为数组末位，j为和的二分之一，输出dp。
到这里就很清晰了，其余分析类似上文，也可看代码注释。
class Solution {
public boolean canPartition(int[] nums) {
//从下标0~i选取其中任意的数字，是否存在一种方案，使其和为j
//如果能够构建这个问题的状态方程，那么推导到i=nums.length-1、j=数组和/2的时候
//dp数组的值就是最终的答案了。
int n = nums.length;
//长度为1，不可分
if(n == 1){
return false;
}
//和为奇数，不可平分
int sum = 0,MaxNum = 0;
for(int num : nums){
sum += num;
MaxNum = Math.max(MaxNum,num);
}
if(sum % 2 == 1){
return false;
}
//如果数组中的最大值，大于了和的1/2，不可平分
int target = sum / 2;
if(MaxNum > target){
return false;
}
//构建动态dp
boolean[][] dp = new boolean[n][target + 1];//画图即可
//初始化：
for(int i = 0; i < n; i++){
dp[i][0] = true;//从0~i索引，选取一种方案能否组成和为0的集合：当然可以，一个数字也不选，这种方案可行
}
dp[0][nums[0]] = true;
for(int i = 1; i < n; i++){
for(int j = 1; j < target + 1; j++){
//先判断能不能选
if(nums[i] > j){
//不能选
dp[i][j] = dp[i - 1][j];
}else{
//能选，需要考虑要不要选
dp[i][j] = dp[i - 1][j] | dp[i - 1][j - nums[i]];
}
}
}
return dp[n - 1][target];
}
}还有非01状态的背包问题等相关多维动态规划问题，以后熟练了再继续写。