完全背包

public class Test02 {
    public static void main(String[] args) {
        int[]value=new int[]{15,20,30};
        int[]weight=new int[]{1,3,4};
        int packageSize=4;
        Test02 test02 = new Test02();
        test02.testPageageProblem(value,weight,packageSize);
    }
    public int testPageageProblem(int[]value,int[]weight,int packageSize){
        //完全背包
        int[]dp=new int[packageSize+1];
        //第一种方式，外层遍历物品，内层遍历背包
        for(int i=0;i<value.length;i++){
            for(int j=weight[i];j<=packageSize;j++){
                dp[j]=Math.max(dp[j],value[i]+dp[j-weight[i]]);
            }
        }
        for (int i : dp) {
            System.out.print(i+" ");
        }
        return dp[packageSize];
    }
    public int testPageageProblem2(int[]value,int[]weight,int packageSize){
        int[]dp=new int[packageSize+1];
        //第二种方式，外层遍历背包，内层遍历物品
        for(int i=1;i<=packageSize;i++){
            for(int j=0;j<value.length;j++){
                if(i-weight[j]>=0){
                    dp[i]=Math.max(dp[i],value[j]+dp[i-weight[j]]);
                }
            }
        }
        for (int i : dp) {
            System.out.print(i+" ");
        }
        return dp[packageSize];
    }
}

518. 零钱兑换 II

int packageSize=amount;
int[]dp=new int[packageSize+1];
dp[0]=1;
for(int i=0;i<coins.length;i++){
  for(int j=coins[i];j<=packageSize;j++){
    dp[j]+=dp[j-coins[i]];
  }
}
return dp[packageSize];
这题必须外层遍历物品，内层遍历背包；否则会有重复计算，比如1+2；2+1

377. 组合总和 Ⅳ

int packageSize=target;
int[]dp=new int[packageSize+1];
//外层遍历背包，内层遍历物品
dp[0]=1;
for(int i=1;i<=packageSize;i++){
  for(int j=0;j<nums.length;j++){
    if(i-nums[j]>=0){
      dp[i]+=dp[i-nums[j]];
    }
  }
}
return dp[packageSize];
//为什么需要外遍历背包，内层遍历物品，因为是排列的总和，所以可以重复计算

322. 零钱兑换

int packageSize=amount;
int[]dp=new int[packageSize+1];
Arrays.fill(dp,Integer.MAX_VALUE);
dp[0]=0;
//外物内包
for(int i=0;i<coins.length;i++){
  for(int j=coins[i];j<=packageSize;j++){
    if(dp[j-coins[i]]!=Integer.MAX_VALUE){
      dp[j]=Math.min(dp[j],dp[j-coins[i]]+1);
    }
  }
}
return dp[packageSize]==Integer.MAX_VALUE?-1:dp[packageSize];

279. 完全平方数

int packageSize=n;
int[]dp=new int[packageSize+1];
for(int i=1;i<dp.length;i++){
  dp[i]=i;
}
//外包内物
for(int i=1;i<=packageSize;i++){
  for(int j=1;j*j<=i;j++){
    dp[i]=Math.min(dp[i-j*j]+1,dp[i]);
  }
}
return dp[packageSize];

139. 单词拆分

int packageSize=s.length();
boolean[]dp=new boolean[packageSize+1];
dp[0]=true;
for(int i=1;i<=packageSize;i++){
  for(int j=0;j<i;j++){
    if(wordDict.contains(s.substring(j,i))&&dp[j]==true){
      dp[i]=true;
    }
  }
}
return dp[packageSize];