背包问题（二）--完全背包

参考资料
背包九讲
https://www.acwing.com/activity/content/11/

完全背包模型

背包容量为V，有N件物品，每件物品的体积是vi，价值是wi，每件物品数量不限。求可以得到的最大价值

思路
同01背包，通过子问题求解
f(i,v)表示前i件物品，在体积不超过v的情况下的最大价值
f(i,v) = max(f(i-1,v-kc[i])+kw[i]) k>=0 v>=kc[i]
c[i]表示第i件物品的体积，w[i]表示第i件物品的价值
即f(i,v)可以表示为选择k个第i件物品，再加上f(i-1,v-kc[i])

如果我们直接这样些的话，复杂度就是个三次方的，可以对方程做等价变换
f(i,v) = max(f(i-1,v) , f(i-1,v-c[i])+wi , f(i-1,v-2c[i]) + 2wi，...)
f(i,v-c[i]) = max( f(i-1,v-c[i]), f(i-1,v-2*c[i]) + wi，... )
将f(i,v-c[i])带入f(i,v)
f(i,v) = max(f(i-1,v) , f(i,v-c[i])+wi))
和01背包的转移方程非常相似 f(i,v) = max(f(i-1,v) , f(i-1,v-c[i])+wi )

代码实现

public static void main(String[] args){
        // 读取数据
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int V = sc.nextInt();
        int[] v = new int[N+1];
        int[] w = new int[N+1];
        for (int i = 0; i < N; i++) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        // 完全背包
        int[][] dp = new int[N+1][V+1];
        // dp[0][0...V] 默认为0
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j <= V; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= v[i]) {
                    dp[i][j] = Math.max(dp[i][j],dp[i][j-v[i]]+w[i]);
                }
            }
        }
        System.out.println(dp[N][V]);
    }

空间复杂度优化
原理同01背包

 for (int i = 1; i <= N; i++) {
      for (int j = v[i]; j <= V; j++) {
            dp[j] = Math.max(dp[j],dp[j-v[i]]+w[i]);
       }
 }
System.out.println(dp[V]);

记录路径

leetcode322题 零钱兑换

题目描述：
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币
个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:

输入: coins = [1, 2, 5], amount = 11
输出: 3 
解释: 11 = 5 + 5 + 1
示例 2:

输入: coins = [2], amount = 3
输出: -1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/coin-change
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路
本质上就是完全背包问题
f(i,v) = min( f(i-1,v-k*c[i])+k)
展开做等价变形
f(i,v) = min(f(i-1,v) , f(i,v-c[i])+1)

代码实现

class Solution {
    public int coinChange(int[] coins, int amount) {
        int N = coins.length;
        int[][] dp = new int[N+1][amount+1];
        int max = amount+1;
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 0;
            for (int j = 1; j < dp[0].length; j++) {
                dp[i][j] = max;
            }
        }

        for(int i=1;i<=N;i++){
            for(int j=0;j<=amount;j++){
                dp[i][j] = dp[i-1][j];
                if(j>=coins[i-1]){
                    dp[i][j] = Math.min(dp[i][j],dp[i][j-coins[i-1]]+1);
                }
            }
        }
        return dp[N][amount]==max ? -1 : dp[N][amount];
    }
}

将数组降维到一维

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

leetcode518题 零钱兑换 II

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 

示例 1:
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2:
输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。

示例 3:
输入: amount = 10, coins = [10] 
输出: 1

注意:
你可以假设：
0 <= amount (总金额) <= 5000
1 <= coin (硬币面额) <= 5000
硬币种类不超过 500 种
结果符合 32 位符号整数

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/coin-change-2
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路
f(i,v) = sum( f(i-1,v-kc[i]) )
展开整理得：
f(i,v) = f(i-1,v) + f(i,v-c[i])

代码实现：

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

空间复杂度优化

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