完全背包问题

在 01 背包基础上，每个物品可以取无数次

• 有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
• 第 i 种物品的体积是 vi，价值是 wi。
• 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
• 输出最大价值。

---

dp[i]表示总体积为i的情况下的最大价值

代码模板

function maxValue(N, V, v, w) {
  let dp = new Array(V + 1).fill(0);
  for (let i = 0; i < N; i++) {
    // 循环物品
    for (let j = v[i]; j <= V; j++) {
      // 循环体积；从小到大；跟01背包问题反过来，表示v[i]可以取多次
      dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
    }
  }
  return dp[V];
}

322. 零钱兑换 (opens new window)

求最少硬币数

class Solution {
    public int coinChange(int[] coins, int V) {
        int n = coins.length;
        int []f = new int[V+1];
        Arrays.fill(f, 0x3f3f3f3f);
        f[0] = 0;
        for (int i = 0; i < n; i++){
            for (int v = coins[i]; v<= V; v++){
                f[v] = Math.min(f[v], f[v-coins[i]]+1);
            }
        }
        return f[V] == 0x3f3f3f3f?-1:f[V] ;
    }
}

拓展：如何打印出最少硬币数的方案？输出一种即可

518. 零钱兑换 II (opens new window)

求兑换的方案数

class Solution {
    public int change(int V, int[] c) {
        int dp[] = new int[V+1];
        dp[0] = 1;

        for (int x : c){
            for (int v = x; v <=V; v++ ){
                dp[v] += dp[v-x];
            }
        }
        return dp[V];
    }
}