完全背包问题
题目描述
有
n件物品和容量为w的背包，给你两个数组weights和values，分别表示第i件物品的重量和价值，每件物品可以放入多次，求解将哪些物品装入背包可使得物品价值总和最大？
完全背包问题和01背包唯一的不同就是物品有无限个， 可以多次放入背包
建立模型
- 确定 dp 数组及下标的含义，数组的含义为从第
[0, i - 1] 个物品中选择物品，其重量和小于等于 j 的最大价值。初始化 dp 数组：
\[\begin{cases} dp[i][0] = 0 \quad (0 \le i < weights.length) \\ dp[0][j] = 0 \quad (0 \le j \le bagSize) \end{cases}
\]
确定递推公式：
\[\begin{cases} dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weights[i - 1]] + values[i - 1]) \quad (j \ge weights[i - 1]) \\ dp[i][j] = dp[i - 1][j] \quad (j < weights[i - 1]) \end{cases}
\]
确定遍历顺序，外循环遍历物品
i -> 1~weights.length ，内循环遍历背包容量 j -> 1~bagSize 。代码实现
public int completeBagProblem(int[] weights, int[] values, int bagSize) {
int n = weights.length;
int[][] dp = new int[n + 1][bagSize + 1];
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= bagSize; j++) {
if (j >= weights[i - 1]) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weights[i - 1]] + values[i - 1]);
}
else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][bagSize];
}
/**
* 状态压缩
* 一维滚动数组实现
*/
public int completeBagProblem(int[] weights, int[] values, int bagSize) {
int[] dp = new int[bagSize + 1];
for (int i = 0; i < weights.length; i++) {
for (int j = weights[i]; j <= bagSize; j++) {
dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
}
}
}
LeeCode 377：组合总和IV
题目描述
给你一个由 不同 整数组成的数组
nums，和一个目标整数target。请你从nums中找出并返回总和为target的元素组合的个数。题目数据保证答案符合 32 位整数范围。顺序不同的序列被视作不同的组合。
数据范围
\(1 \le nums.length \le 200\)
\(1 \le nums[i] \le 1000\)
\(1 \le target \le 1000\)
nums 中元素互不相同
建立模型
该问题有两个关键特征：
元素可以多次选择，属于完全背包问题
不同的选择顺序视为不同的组合，属于排列问题
问题转化 \(\Rightarrow\) 完全背包问题
物品 \(\rightarrow\) 数组中的元素，价值和重量都是 nums[i]
背包容量 \(\rightarrow\) 目标整数
模型建立
- 确定 dp 数组及下标的含义，数组的含义为组合成目标整数
j 的方法数。初始化 dp 数组，
dp[0] = 1，表示组合成目标整数0只有一种方法，空集。确定递推公式：
dp[j] = dp[j] + dp[j - nums[i]]确定遍历顺序：外循环遍历背包容量
j -> 1~target，内循环遍历物品 i -> 0 ~ nums.length - 1 。为什么是外循环遍历背包容量呢？
从题目描述中分析，当前问题属于一个排列问题，即不同的添加顺序属于不同的组合。如果外循环遍历物品，添加物品时只能按照 nums 中元素的相对顺序添加，无法得到不同的顺序；反之，外循环遍历背包容量，每次循环都可以考虑所有的物品。
Example
上面的话可能不好理解，举个例子说明，nums = {1, 2, 3}，target = 4。
如果外循环遍历物品，那么只会出现 {1, 3}，而不会出现 {3, 1}。
如果外循环遍历背包容量，则会出现 {1, 3} 和 {3, 1}。
总结下来，可以得到以下两个结论：
排列问题：外循环遍历背包容量，内循环遍历物品
组合问题：外循环遍历物品，内循环遍历背包容量
代码实现
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
/**
* 排列问题，先遍历背包容量，后遍历物品
*/
for (int j = 1; j <= target; j++) {
for (int i = 0; i < nums.length; i++) {
if (j >= nums[i]) {
dp[j] += dp[j - nums[i]];
}
}
}
return dp[target];
}
LeeCode 518：零钱兑换
题目描述
给你一个整数数组
coins表示不同面额的硬币，另给一个整数amount表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回
0。假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带符号整数。
建立模型
问题转换 \(\Rightarrow\) 完全背包问题
物品 \(\rightarrow\) 硬币，价值和重量都是 coins[i]
背包容量 \(\rightarrow\) 总金额
该问题描述等价于从 conis 中选择若干个硬币，使其等于总金额的方法数，每个硬币可以选择多次，且不同的选择顺序视为同一方法，属于组合问题。
代码实现
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];
}
LeeCode 279：完全平方数
题目描述
给你一个整数
n，返回 和为 n 的完全平方数的最少数量 。完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
建立模型
问题转化 \(\Rightarrow\) 完全背包问题
该问题描述等价于从 [1, 4, 9, ..., \(\lfloor \sqrt{n} \rfloor^{2}\)] 这些完全平方数中选择若干个数，使其和等于 n 的最少个数，且每个完全平方数可多次选择。
物品 \(\rightarrow\) 完全平方数
背包容量 \(\rightarrow\) 整数 n
代码实现
public int numSquares(int n) {
int[] dp = new int[n + 1];
dp[0] = 0;
for (int i = 1; i <= n; i++) {
dp[i] = Integer.MAX_VALUE;
}
for (int i = 1; i * i <= n; i++) {
for (int j = i * i; j <= n; j++) {
if (dp[j - i * i] != Integer.MAX_VALUE) {
dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
}
}
}
return dp[n];
}
LeeCode 139：单词拆分
题目描述
给你一个字符串
s和一个字符串列表wordDict作为字典。请你判断是否可以利用字典中出现的单词拼接出s。注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
建立模型
问题转化 \(\Rightarrow\) 完全背包问题
该问题描述等价于从字典中选择若干个字符串，是否可以拼接成字符串 s ，且字典中的字符串可多次使用。
物品 \(\rightarrow\) 字典中的字符串
背包容量 \(\rightarrow\) 字符串 s
模型建立
- 确定 dp 数组及下标含义，数组的含义为 由字符串 s 中下标
0 ~ i - 1 构成的子串是否能字典中的单词拼接。初始化 dp 数组，\(dp[0] = true\)，表示空串可由字典中的单词拼接
确定递推公式：\(dp[i] = wordDict.contains(s.substring(j, i))\ \&\&\ dp[j]\)
确定遍历顺序，枚举子串的结束位置和单词的起始位置。
代码实现
public boolean wordBreak(String s, List<String> wordDict) {
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
// i -> 子串结束位置, j 子串起始位置
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
String temp = s.substring(j, i);
if (wordDict.contains(temp) && dp[j]) {
dp[i] = true;
}
}
}
return dp[s.length()];
}
