完全背包问题

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

思路

完全背包和01背包只有遍历顺序上有所不同，其余步骤都是一样的。

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。根据上一篇文章的分析其实很明显了，为了避免dp[i][j]覆盖上一行dp[i-1][j]，只能从右到左遍历。但在完全背包中，每个物品能无限使用，所以我们就是要覆盖它，来达到无限选择的目的。

还有一个问题，“无限选择”，我看代码里是个for循环，没有“无限”啊。实际上，是因为这里所有物品的weight都是正整数，每次容量j++，就已经考虑一次了。实际上，没有无限一说，万物皆有代价。

代码

public int WeightBag(int[] weight, int[] value, int bagWeight){
    // 定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
    int[] dp = new int[bagWeight + 1];
    // 遍历顺序：外层遍历物品，内层遍历背包容量
    // 针对初始化第0行，其实已经包括在这里面了
    for (int i = 0; i < weight.length; i++){
        for (int j = bagWeight; j >= weight[i]; j--){
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    return dp[bagWeight];
}

完全背包变种

518. 零钱兑换 II

力扣链接

在完全背包问题中，有两种结果：组合数和排列数，我们需要根据题意判断出是哪一种。本题明确指出了组合数。

那么这两种在代码上有什么区别呢？

其实就是在遍历的顺序上有所区别，组合数需要外层物品内层背包，排列数则相反，我们可以从排列来理解。物品a和b，外层背包内层物品才会出现，ab和ba两种遍历顺序，这是我们想要的效果，而外层物品内层背包不会有这样的效果。

public int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;
    for(int i = 0; i < coins.length; i++){
    	for(int j = coins[i]; j <= amount; j++){
    		dp[j] += dp[j - coins[i]];
    	}
    }
    return dp[amount];
}

377. 组合总和 Ⅳ

力扣链接

标题是组合，实际求的是排列数。

public int combinationSum4(int[] nums, int target) {
    int[] dp = new int[target + 1];
    dp[0] = 1;
    for (int i = 0; i <= target; i++) {
    	for (int j = 0; j < nums.length; j++) {
    		if (i - nums[j] >= 0) {
    			dp[i] += dp[i - nums[j]];
    		}
    	}
    }
    return dp[target];
}

322. 零钱兑换

力扣链接

dp数组需要初始化为最大值MAX，在本题中，全是1元硬币时需要amount个，那么MAX = amount+1。dp[0]没有实际意义，可以从定义出发：兑换0元需要0个硬币；也可以从递推出发：后面的结果都来自dp[0]，它必须为0。

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    int MAX = amount + 1;
    Arrays.fill(dp, MAX);
    dp[0] = 0;
    for (int i = 0; i < coins.length; i++) {
        for (int j = coins[i]; j <= amount; j++) {
            dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
        }
    }
    return dp[amount] == MAX ? -1 : dp[amount];
}

279. 完全平方数

力扣链接

平方数就是物品，n是背包容量。

public int numSquares(int n) {
    int[] dp = new int[n + 1];
    int MAX = n;
    Arrays.fill(dp, MAX);
    dp[0] = 0;
    for(int i = 1; i*i <= n; i++){
        for(int j = i*i; j <= n; j++){
            dp[j] = Math.min(dp[j], dp[j - i*i]+1);
        }
    }
    return dp[n];
}

139. 单词拆分

力扣链接

public boolean wordBreak(String s, List<String> wordDict) {
    boolean[] dp = new boolean[s.length()+1];
    dp[0] = true;
    for(int i = 0; i <= s.length(); i++){
        for(int j = 0; j < wordDict.size(); j++){
            String word = wordDict.get(j);
            int ws = word.length();
            if(i - ws >= 0 && dp[i - ws] && s.substring(i - ws, i).equals(word)){
                dp[i] = true;
            }
        }
    }
    return dp[s.length()];
}