最后一块石头的重量 II（0-1背包问题

将石头尽可能分为两堆重量一样的，进行相撞则为0

class Solution {public int lastStoneWeightII(int[] stones) {int sum=0;for(int x:stones){sum+=x;}int target=sum/2;int[] dp=new int[target+1];//dp[j]表示最大石堆的重量,j表示背包的容量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])-dp[target];}
}

目标和（分为两堆数组，正和负，求出正的有多少种组合即可

一和零（相当于是一维数组的思路，二维数组的属性

  M和n代表，物品的两种属性

class Solution {public int findMaxForm(String[] strs, int m, int n) {int[][] dp=new int[m+1][n+1];//dp[i][j]记录有i个0，j个1。最多有几个子集for(String s:strs){//遍历每个字符串,相当于遍历物品int x=0,y=0;//统计0和1的个数for(char c:s.toCharArray()){if(c=='0'){x++;}if(c=='1'){y++;}}for(int i=m;i>=x;i--){//遍历背包容量，倒序遍历,比当前字符串0和1多，才能减去for(int j=n;j>=y;j--){dp[i][j]=Math.max(dp[i][j],dp[i-x][j-y]+1);}}}return dp[m][n];}
}