【动态规划】完全背包问题
【动态规划】完全背包问题
1. DP42 【模板】完全背包
完全背包和 01 背包不同的就是每个物品可以选任意多次，01 背包是只能选 1 次或者不选，这道题也是分为恰好装满和可以不装满两个问题
状态表示：
还是和 01 背包的状态表示一样，dp[i][j] 表示从前 i 个物品中选，总体积不超过 j 的所有选法的最大值
状态转移方程：
因为这里一个物品可以选择多次，所以也就分为选 1,2,3,4,······等多种情况，每一次都需要减去相应倍数的体积，同时也要加上相应倍数的价值
在之前做通配符匹配时，关于这种状态转移方程的优化是利用了数学变换来做的，这道题也可以这样优化：
初始化：和 01 背包那里一样，i = 0 时，表示有 0 个物品，那么 dp[0][j] 这一行就都是 0，而 j = 0 时，由于只有 j >= v[i] 才能进行接下来的判断，所以 j = 0 这一列不用初始化，不会判断到 j < 0 之外的数据
返回值：dp[n][V]
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt(), V = in.nextInt();
int[] w = new int[n + 1];
int[] v = new int[n + 1];
for (int i = 1; i <= n; i++) {
v[i] = in.nextInt();
w[i] = in.nextInt();
}
int[][] dp1 = new int[n + 1][V + 1];
for (int i = 1; i <= n; i++ ) {
for (int j = 0; j <= V; j++) {
dp1[i][j] = dp1[i - 1][j];
if (j >= v[i]) {
dp1[i][j] = Math.max(dp1[i][j], dp1[i][j - v[i]] + w[i]);
}
}
}
System.out.println(dp1[n][V]);
int[][] dp2 = new int[n + 1][V + 1];
for (int i = 1; i <= V ; i++ ) dp2[0][i] = -1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= V; j++) {
dp2[i][j] = dp2[i - 1][j];
if (j >= v[i] && dp2[i][j - v[i]] != -1) {
dp2[i][j] = Math.max(dp2[i][j], dp2[i][j - v[i]] + w[i]);
}
}
}
System.out.println(dp2[n][V] == -1 ? 0 : dp2[n][V]);
}
}空间优化：还是和 01 背包一样，使用一维的滚动数组来进行优化，但是有一点还是不同的
这里需要用到上一行的同一列，和同一列左边的数据，所以说在用一维数组来填表的时候，是需要用到左边更新数据之后的，而 01 背包是需要用到更新之前的，所以是从右往左填，那么完全背包的优化就是从左到右填
还可以再把写法简化一下：
在之前，把不能凑出目标值的情况初始化为了 -1，然后循环里进行判断是否是 -1，可以直接在初始化时就把不符合的元素初始化为一个很小的值，后面填表求最大值时就不会用到这个值，最后返回值直接判断是否小于 0 即可
2. 零钱兑换
这道题其实就是完全背包问题，一个硬币可以选多次，找出使用个数最少的硬币组合，那么状态表示就可以定义为：
dp[i][j] 表示从 i 个硬币中挑选，总和正好等于 j 的最少的硬币个数
状态转移方程和初始化，返回值都和上面的完全背包问题类似，只不过这道题要求的是最小值，所以初始化时如果凑不出 j ，要初始化为一个很大的数，这样才不会影响取最小值
class Solution {
public int coinChange(int[] coins, int amount) {
int n = coins.length;
int[] dp = new int[amount + 1];
for(int j = 1; j <= amount; j++) dp[j] = 0x3f3f3f3f;
for(int i = 1; i <= n; i++){
for(int j = coins[i - 1];j <= amount; j++){
if(dp[j - coins[i - 1]] != 0x3f3f3f3f){
dp[j] = Math.min(dp[j],dp[j - coins[i - 1]] + 1);
}
}
}
return dp[amount] >= 0x3f3f3f3f ? -1 : dp[amount];
}
}3. 零钱兑换 II
这道题还是完全背包的模型，状态表示：
dp[i][j] 表示从 i 个硬币中挑选，总和正好等于 j 有多少种选法
状态转移方程：
由于是求一共有多少种选法，所以需要把所有的情况都加起来
初始化：除了第一个位置 dp[0][0] 初始化为 1，其他位置都不用初始化
返回值：dp[n][j]
还是直接看空间优化版本的代码：
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];
}
}4. 完全平方数
还是完全背包的模型，这不过这次需要挑选的数变成了平方数，状态表示：
dp[i][j] 表示从 i 个完全平方数中挑选，总和正好等于 j 的最少的个数
状态转移方程：
初始化：初始化时还是如果凑不出 j ，要初始化为一个很大的数，这样才不会影响取最小值
class Solution {
public int numSquares(int n) {
int aim = (int)Math.sqrt(n);
int[] dp = new int[n + 1];
for(int j = 1;j <= n; j++) dp[j] = 0x3f3f3f3f;
for (int i = 1; i <= aim; i++){
for(int j = i * i;j <= n ;j++){
dp[j] = Math.min(dp[j],dp[j - i * i] + 1);
}
}
return dp[n] == 0x3f3f3f3f ? 0 : dp[n];
}
}腾讯云开发者
