完全背包

【题目】有N种物品，一个容量为C的背包，每个物品都有无限件，第i件物品的价值为v[i]，重量为w[i]，求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
【分析】在0-1背包的基础上，增加无限次选定的特点。

  1. class Main {
  2.     //直接一维优化
  3.     public int maxValue(int N, int C, int[] value, int weight[]) {
  4.         int[] dp = new int[C+1];
  5.         for (int i = 0; i < N; i++) {
  6.             for (int j = 0; j <= C; j++) {
  7.                 int noSelect = dp[j];
  8.                 int doSelect = j>=weight[i] ? dp[j-weight[i]]+value[i] : 0;
  9.                 dp[j] = Math.max(noSelect, doSelect);
  10.             }
  11.         }
  12.         return dp[C];
  13.     }
  14. }

【题目】LeetCode上的279，完全平方数，难度Medium

给定正整数n，找到若干个完全平方数，比如1，4，9，16，使得他们的和等于n，你需要让组成的完全平方数的个数最少。简述：给你一个整数n，返回和为n的完全平方数的【最少数量】。

class Solution {
    //朴素做法，不要这种做法
    public int numSquares(int n) {
        //先构建完全平方数数组
        List<Integer> list = new ArrayList<>();
        int num = 1;
        while (num*num <= n) {
            list.add(num*num);
            num++;
        }
        //完全背包
        //最大容量为n，物品价值和体积是list元素
        int c = list.size();
        int[][] dp = new int[c][n+1]; //存储的是最少数量
        //base case
        for (int j=0; j<=n; j++) {
            int temp = list.get(0); //获取第一个元素
            int k = j / temp;  //容量为temp倍数
            if (j == k*temp) { //能够凑整才行
                dp[0][j] = k;
            } else {
                dp[0][j] = -1;
            }
        }
        //处理剩余情况
        for (int i=1; i<c; i++) { //类别
            int t = list.get(i);
            for (int j=0; j<=n; j++) {
                //不选
                dp[i][j] = dp[i-1][j];
                //选择k次i
                for (int k=1; k*t<=j; k++) {
                    if (dp[i-1][j-k*t] != -1) {
                        dp[i][j] = Math.min(dp[i][j], dp[i-1][j-k*t]+k);
                    }
                }
            }
        }
        return dp[c-1][n];
    }
}

class Solution {
    //一维优化
    public int numSquares(int n) {
        //先构建完全平方数数组
        List<Integer> list = new ArrayList<>();
        int num = 1;
        while (num*num <= n) {
            list.add(num*num);
            num++;
        }
        //完全背包
        //最大容量为n，物品价值和体积是list元素
        int c = list.size();
        int[] dp = new int[n+1]; //到当前j位置，存储的是最少数量
        //base case
        for (int j=0; j<=n; j++) {
            int temp = list.get(0); //获取第一个元素
            int k = j / temp;  //容量为temp倍数
            if (j == k*temp) { //能够凑整才行
                dp[j] = k;
            } else {
                dp[j] = -1;
            }
        }
        //处理剩余情况
        for (int i=1; i<c; i++) { //类别
            int t = list.get(i);
            for (int j=t; j<=n; j++) {
                if (dp[j-t] != -1) {
                    //选择和不选择
                    dp[j] = Math.min(dp[j], dp[j-t]+1);
                }
            }
        }
        return dp[n];
    }
}

【题目】LeetCode上的322，零钱兑换，难度Medium

给不同面额的硬币coins，和一个总额度amount，编写一个函数来计算可以凑成总金额所需的最少硬币个数，如果没有任何一种硬币组合能组成总金额，则返回-1。可以认为每种硬币的数量是无限的。

class Solution {
    public int coinChange(int[] coins, int amount) {
        //多重背包问题
        int[] dp = new int[amount+1]; //构成j的最少数量
        int INF = Integer.MAX_VALUE / 2;
        //base case，处理第一个
        for (int j=0; j<=amount; j++) {
            int temp = j / coins[0];
            if (temp * coins[0] == j) {
                dp[j] = temp;
            } else {
                dp[j] = INF;
            }
        }
        int n = coins.length;
        for (int i=1; i<n; i++) {
            int coin = coins[i];
            for (int j=coin; j<=amount; j++) {      
                dp[j] = Math.min(dp[j], dp[j-coin]+1);
            }
        }
        return dp[amount] == INF ? -1 : dp[amount];
    }
}


class Solution {
    public int coinChange(int[] coins, int amount) {
        //多重背包问题
        int[] dp = new int[amount+1]; //构成j的最少数量
        int INF = Integer.MAX_VALUE / 2;
        //base case，处理第一个
        // for (int j=0; j<=amount; j++) {
        //     int temp = j / coins[0];
        //     if (temp * coins[0] == j) {
        //         dp[j] = temp;
        //     } else {
        //         dp[j] = INF;
        //     }
        // }
        for(int i=1; i<=amount; i++) dp[i] = INF; //背包容量为0为有效值
        int n = coins.length;
        for (int i=0; i<n; i++) {
            int coin = coins[i];
            for (int j=coin; j<=amount; j++) {      
                dp[j] = Math.min(dp[j], dp[j-coin]+1);
            }
        }
        return dp[amount] == INF ? -1 : dp[amount];
    }
}

【题目】LeetCode上的518，零钱兑换Ⅱ，难度为Medium。

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
【分析】这道题可以使用dfs做，也可以使用完全背包做。

class Solution {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        //完全背包，朴素实现会超时，22/28的通过率
        //修改dp定义，前i种硬币，凑成j的组合数
        int[][] dp = new int[n][amount+1];
        //base case，处理第1个
        for (int j=0; j<=amount; j++) {
            int k = j / coins[0];
            if (k * coins[0] == j) { //可以凑成
                dp[0][j] = 1;
            } else {
                dp[0][j] = 0;
            }
        }

        //处理剩余的
        for (int i=1; i<n; i++) {
            int coin = coins[i];
            for (int j=0; j<=amount; j++) {
                //不选该硬币
                int noSelect = dp[i-1][j];
                //选择
                int doSelect = 0;
                for (int k=1; k<=j; k++) {
                    int temp = k / coin;
                    if (temp * coin == k) {
                        doSelect += dp[i-1][j-k];
                    }
                }
                dp[i][j] = noSelect + doSelect;
            }
        }
        return dp[n-1][amount];
    }
}

class Solution {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        //完全背包，朴素实现，这种会通过测试用例
        //修改dp定义，前i种硬币，凑成j的组合数
        int[][] dp = new int[n][amount+1];
        //base case，处理第1个
        for (int j=0; j<=amount; j++) {
            int k = j / coins[0];
            if (k * coins[0] == j) { //可以凑成
                dp[0][j] = 1;
            } else {
                dp[0][j] = 0;
            }
        }

        //处理剩余的
        for (int i=1; i<n; i++) {
            int coin = coins[i];
            for (int j=0; j<=amount; j++) {
                //不选该硬币
                dp[i][j] = dp[i-1][j];
                //选择
                for (int k=1; k*coin<=j; k++) {
                    dp[i][j] += dp[i-1][j-k*coin];
                }
            }
        }
        return dp[n-1][amount];
    }
}

class Solution {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        //完全背包，一维优化
        //修改dp定义，前i种硬币，凑成j的组合数
        int[] dp = new int[amount+1];
        //base case，处理第1个
        for (int j=0; j<=amount; j++) {
            int k = j / coins[0];
            if (k * coins[0] == j) { //可以凑成
                dp[j] = 1;
            } else {
                dp[j] = 0;
            }
        }
        //处理剩余的
        for (int i=1; i<n; i++) {
            int coin = coins[i];
            for (int j=coin; j<=amount; j++) {
                dp[j] += dp[j-coin];
            }
        }
        return dp[amount];
    }
}