01背包问题

  1. public class Test02 {
  2.     public static void main(String[] args) {
  3.         int[]value=new int[]{15,20,30};
  4.         int[]weight=new int[]{1,3,4};
  5.         int packageSize=4;
  6.         Test02 test02 = new Test02();
  7.         test02.testPageageProblem(value,weight,packageSize);
  8.     }
  9.     public int testPageageProblem(int[]value,int[]weight,int packageSize){
  10.         int[]dp=new int[packageSize+1];
  11.         for(int i=0;i<value.length;i++){
  12.             for(int j=packageSize;j>=weight[i];j--){
  13.                 dp[j]=Math.max(dp[j],value[i]+dp[i-weight[i]]);
  14.             }
  15.         }
  16.         return dp[packageSize];
  17.     }
  18. }

416. 分割等和子集

  1. int sum=0;
  2. for (int num : nums) {
  3.   sum+=num;
  4. }
  5. int packageSize=0;
  6. if(sum%2==1){
  7.   return false;
  8. }else{
  9.   packageSize=sum/2;
  10. }
  11. int[]dp=new int[packageSize+1];
  12. for(int i=0;i<nums.length;i++){
  13.   for(int j=packageSize;j>=nums[i];j--){
  14.     dp[j]=Math.max(dp[j],nums[i]+dp[j-nums[i]]);
  15.   }
  16. }
  17. return dp[packageSize]==packageSize;

1049. 最后一块石头的重量 II

  1. int sum=0;
  2. for (int stone : stones) {
  3.   sum+=stone;
  4. }
  5. int packageSize=sum/2;
  6. int[]dp=new int[packageSize+1];
  7. for(int i=0;i<stones.length;i++){
  8.   for(int j=packageSize;j>=stones[i];j--){
  9.     dp[j]=Math.max(dp[j],stones[i]+dp[j-stones[i]]);
  10.   }
  11. }
  12. int nowWeight=dp[packageSize];
  13. int rest=sum-nowWeight;
  14. return Math.abs(rest-nowWeight);

494. 目标和

  1. int sum=0;
  2. for (int num : nums) {
  3.   sum+=num;
  4. }
  5. sum+=target;
  6. if(sum%2==1||sum<0){
  7.   return 0;
  8. }
  9. int packageSize=sum/2;
  10. int[]dp=new int[packageSize+1];
  11. dp[0]=1;
  12. for(int i=0;i<nums.length;i++){
  13.   for(int j=packageSize;j>=nums[i];j--){
  14.     dp[j]+=dp[j-nums[i]];
  15.   }
  16. }
  17. return dp[packageSize];

474. 一和零

  1. int[][]dp=new int[m+1][n+1];
  2. for (String str : strs) {
  3.   char[] chars = str.toCharArray();
  4.   int zeroCount=0;
  5.   int oneCount=0;
  6.   for(int i=0;i<chars.length;i++){
  7.     if(chars[i]=='1'){
  8.       oneCount++;
  9.     }else{
  10.       zeroCount++;
  11.     }
  12.   }
  13.   for(int i=m;i>=zeroCount;i--){
  14.     for(int j=n;j>=oneCount;j--){
  15.       dp[i][j]=Math.max(dp[i][j],dp[i-zeroCount][j-oneCount]+1);
  16.     }
  17.   }
  18. }
  19. return dp[m][n];