动态规划算法专题（九）：完全背包问题
目录
1. 【模板】完全背包
1.1 算法原理
1.2 算法代码
1.3 空间优化
1.4 空间优化版本代码
2. 零钱兑换
2.1 算法原理
2.2 算法代码
3. 零钱兑换 II
3.1 算法原理
3.2 算法代码
4. 完全平方数
4.1 算法原理
4.2 算法代码
完全背包问题的初始化与 01 背包的初始时相同:
第一行需要初始化,
第一列不需额外初始化, 在填表时一同填入即可(存在条件判定, 不会发生越界)
1. 【模板】完全背包
【模板】完全背包_牛客题霸_牛客网
1.1 算法原理
- 状态表示:
dp[i][j] : 从前 i 个数中选, 总体积不超过 j , 所有选法中, 最大价值(第一问)
dp[i][j] : 从前 i 个数中选, 总体积等于 j , 所有选法中, 最大价值(第二问)
- 状态转移方程:
dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i])
- 初始化
如下图.
- 建表顺序:
从上往下每一行,
从左往右每一列
- 返回值
1) dp[n][V]
2) dp[n][V] == -1 ? 0 : dp[n][V]
1.2 算法代码
import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt(); // 物品个数int large = in.nextInt(); // 背包体积int[] V = new int[n];int[] W = new int[n];for(int i = 0; i < n; i++) {V[i] = in.nextInt();W[i] = in.nextInt();}// 第一问int[][] dp = new int[n + 1][large + 1];for(int i = 1; i <= n; i++) {for(int j = 0; j <= large; j++) {dp[i][j] = dp[i - 1][j];if(j >= V[i - 1]) dp[i][j] = Math.max(dp[i][j], dp[i][j - V[i - 1]] + W[i - 1]);}}System.out.println(dp[n][large]);// 第二问// 初始化for(int j = 1; j <= large; j++) dp[0][j] = -1;// 填表for(int i = 1; i <= n; i++) {for(int j = 0; j <= large; j++) {dp[i][j] = dp[i - 1][j];if(j >= V[i - 1] && dp[i][j - V[i - 1]] != -1) dp[i][j] = Math.max(dp[i][j], dp[i][j - V[i - 1]] + W[i - 1]);}}System.out.println(dp[n][large] == -1 ? 0 : dp[n][large]);}
}1.3 空间优化
完全背包优化时, 遍历顺序与 01 背包不同, 需从左往右遍历填表.
1.4 空间优化版本代码
import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息/*** 空间优化* @param args*/public static void main1(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt(); // 物品个数int large = in.nextInt(); // 背包体积int[] V = new int[n];int[] W = new int[n];for(int i = 0; i < n; i++) {V[i] = in.nextInt();W[i] = in.nextInt();}// 第一问int[] dp = new int[large + 1];for(int i = 1; i <= n; i++) {for(int j = V[i - 1]; j <= large; j++) {dp[j] = Math.max(dp[j], dp[j - V[i - 1]] + W[i - 1]);}}System.out.println(dp[large]);// 第二问// 初始化for(int j = 1; j <= large; j++) dp[j] = -0x3f3f3f3f;// dp[j] = -1;// 填表for(int i = 1; i <= n; i++) {for(int j = V[i - 1]; j <= large; j++) {// if(dp[j - V[i - 1]] != -1)dp[j] = Math.max(dp[j], dp[j - V[i - 1]] + W[i - 1]);}}System.out.println(dp[large] < 0 ? 0 : dp[large]);}
}2. 零钱兑换
. - 力扣（LeetCode）
2.1 算法原理
- 状态表示:
dp[i][j]: 从前 i 个礼物中选, 体积不超过 j 的所有选法中, 最大价值
dp[i][j]: 从前 i 个硬币中选, 恰好凑成 j 的所有选法中, 最少硬币个数
- 状态转移方程:
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coins[i]] + 1)
- 初始化
只需初始化第一行.
无效状态使用 0x3f3f3f3f 表示(防止溢出)
- 建表顺序:
从上往下每一行,
从左往右每一列
- 返回值:
dp[n][amount] >= INF ? -1 : dp[n][amount]
2.2 算法代码
class Solution {public int coinChange(int[] coins, int amount) {int INF = 0x3f3f3f3f;int n = coins.length;int[][] dp = new int[n + 1][amount + 1];for(int j = 1; j <= amount; j++) dp[0][j] = INF;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] >= INF ? -1 : dp[n][amount];}/*** 空间优化* @param coins* @param amount* @return*/public int coinChange1(int[] coins, int amount) {int INF = 0x3f3f3f3f;int n = coins.length;int[] dp = new int[amount + 1];for(int j = 1; j <= amount; j++) dp[j] = INF;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] >= INF ? -1 : dp[amount];}
}3. 零钱兑换 II
. - 力扣（LeetCode）
3.1 算法原理
- 状态表示:
dp[i][j]: 从前 i 个数中选, 能凑成 j 的选法的总数
- 状态转移方程:
不选 i --> dp[i - 1][j]
选1个 i --> dp[i - 1][j - coins[i]]
选2个 i --> dp[i - 1][j - 2*coins[i]]
.......
dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]]
- 初始化
只初始化第一行, 当 j == 0 时, dp[0][0] = 1;
- 建表顺序:
从上往下每一行,
从左往右每一列
- 返回值:
dp[n][amount]
3.2 算法代码
class Solution {public int change(int amount, int[] coins) {int n = coins.length;int[][] dp = new int[n + 1][amount + 1];dp[0][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];}/*** 空间优化*/public int change1(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];}
}4. 完全平方数
. - 力扣（LeetCode）
4.1 算法原理
- 状态表示:
dp[i][j]: 从前 i 个物品中挑选, 容量不超过 j , 所有选法中, 最大价值(完全背包)
dp[i][j]: 从前 i 个完全平方数中挑选, 总和等于 j , 所有选法中, 最小数量
- 状态转移方程:
不选 i*i --> dp[i - 1][j]
选1个 i*i --> dp[i - 1][j - i*i] + 1
选2个 i*i --> dp[i - 1][j - 2*i*i] + 2
.......
dp[i][j] = min(dp[i - 1][j], dp[i][j - i*i] + 1)
- 初始化
只初始化第一行(没有完全平方数时)
- 建表顺序:
从上往下每一行,
从左往右每一列
- 返回值:
dp[Math.sqrt(n)][n]
4.2 算法代码
class Solution2 {public int numSquares(int n) {int INF = 0x3f3f3f3f;int m = (int)Math.sqrt(n);int[][] dp = new int[m + 1][n + 1];for(int j = 1; j <= n; j++) dp[0][j] = INF;for(int i = 1; i <= m; i++) {for(int j = 0; j <= n; j++) {dp[i][j] = dp[i - 1][j];if(j - i * i >= 0) dp[i][j] = Math.min(dp[i][j], dp[i][j - i * i] + 1); }}return dp[m][n];}/*** 空间优化* @param n* @return*/public int numSquares1(int n) {int INF = 0x3f3f3f3f;int m = (int)Math.sqrt(n);int[] dp = new int[n + 1];for(int j = 1; j <= n; j++) dp[j] = INF;for(int i = 1; i <= m; i++) {for(int j = i * i; j <= n; j++) {dp[j] = Math.min(dp[j], dp[j - i * i] + 1);}}return dp[n];}
}END