今天是01背包的应用题，讲述了01背包的不同应用方法
首先经典01背包，讲的是容量为j的背包能装下的最大价值为dp[j]
切割等和子集，讲的是容量为j的背包能不能给它装满
最后一块石头的重量 II ，讲的是容量为j的背包，尽可能的装，能装多少是多少，有点像经典01背包的最大价值
目标和，讲的是给定容量为j的背包，装满这个背包有多少种方法
一和零，讲的是装满给定容量的背包，最多有多少物品
最后一块石头的重量 II
动规应用题，主要是怎么将这道题分析出来使用动规方法来做，要完全理解题目，才能想到这个方法，将石头分为尽可能重量相等的两堆，设每一堆重量为target，看看给定容量为target的背包，尽可能能装多少，最后剩下的就是最后一块石头的重量了。
动规五部曲：
- dp[j]代表的是容量为j的背包所能装下的最大重量为dp[j]
- 递推公式：dp[j]=max(dp[j],dp[j-weight[i]]+value[i])
- 初始化，根据dp数组的含义，全都初始化为0
- 遍历顺序，从大到小
class Solution {
public int lastStoneWeightII(int[] stones) {
int sum=0;
for(int i=0;i<stones.length;i++){
sum+=stones[i];
}
int target=sum/2;
int[] dp=new int[target+1];
for(int i=0;i<stones.length;i++){
for(int j=target;j>=stones[i];j--){
dp[j]=Math.max(dp[j],dp[j-stones[i]]+stones[i]);
}
}
return sum-dp[target]*2;
}
}目标和
这一题，需要根据题意进行数学推导，将问题进行转换，不然看不出来该怎么解决。
既然要使元素和为target，那么将数组进行分组，分为左右两组，于是有公式：left-right=target，left+right=sum;根据这两个公式可推出：left=(sum+target)/2;而sum和target是固定的，于是只有left是变化了，问题就转化为装满容量为left的背包有多少种方法？
五部曲
dp[j]表示装满容量为j的背包有dp[j]种方法
递推公式：dp[j]+=dp[j-nums[i]];
只要搞到nums[i]，凑成dp[j]就有dp[j - nums[i]] 种方法。
例如：dp[j]，j 为5，
已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 容量为5的背包。
已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 容量为5的背包。
已经有一个3（nums[i]） 的话，有 dp[2]中方法 凑成 容量为5的背包
已经有一个4（nums[i]） 的话，有 dp[1]中方法 凑成 容量为5的背包
已经有一个5 （nums[i]）的话，有 dp[0]中方法 凑成 容量为5的背包
那么凑整dp[5]有多少方法呢，也就是把 所有的 dp[j - nums[i]] 累加起来。
初始化：根据dp数组含义，dp[o]应该为1；而其他的都为0；便于后面更新覆盖
遍历顺序：从后向前
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum=0;
for(int i=0;i<nums.length;i++){
sum+=nums[i];
}
//如果target的绝对值大于sum，没有组合
if(Math.abs(target)>sum) return 0;
//如果target+sum的和不能整除2，就意味着左子集和为小数，没有组合
if((target+sum)%2!=0) return 0;
int left=(target+sum)/2;
int[] dp=new int[left+1];
dp[0]=1;
for(int i=0;i<nums.length;i++){
for(int j=left;j>=nums[i];j--){
dp[j]+=dp[j-nums[i]];
}
}
return dp[left];
}
}一和零
这一题也是完全看不出来该怎么用动规方法。分析题目，子集中要有m个0，n个1，要求子集的最大长度，也就是元素最多有几个。那么就把m和n看成是两个容器，分别来装0和1，看装满这两个容器，里面最多有多少个物品
动规五部曲：
- dp[i][j]代表的是装满容量为i和j的背包，能放的最多物品数为dp[i][j]
- 递推公式：dp[i][j]=max(dp[i][j],dp[i-x][j-y]+1);x代表物品中0的个数，y代表物品中1的个数，+1代表物品数加一
- 初始化，全都初始化成0；
- 遍历顺序：从后往前
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp=new int[m+1][n+1];
for(int i=0;i<strs.length;i++){
int x=0,y=0;
for(int j=0;j<strs[i].length();j++){
if(strs[i].charAt(j)=='0'){
x++;
}else{
y++;
}
}
for(int p=m;p>=x;p--){
for(int q=n;q>=y;q--){
dp[p][q]=Math.max(dp[p][q],dp[p-x][q-y]+1);
}
}
}
return dp[m][n];
}
}
