动态规划之完全背包问题解题方法

动态规划之完全背包问题解题方法

完全背包是经过01背包演变而来的,区别就是完全背包问题中物品是有无限个的,也就是说一个物品可以放入背包多次。同样的LeetCode上也没有纯完全背包的问题,都是完全背包应用方面的题目,也就是需要将其转化为完全背包问题。所以,记录一下从代码随想录-完全背包理论基础学习到纯完全背包问题的解题方法,补充一下纯完全背包的二维dp数组的解法,具体应用题需要靠自己来将其转化成完全背包,dp数组状态转移方程、初始化、遍历顺序可能会和纯完全背包问题有一些不同,需要具体问题具体分析。

背包问题

概念

有n件物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i],得到的价值是value[i]每件物品有无限个,即一个物品可以放入背包多次,求解将哪些物品装入背包里物品价值总和最大。

例子

背包最大重量为4,每个物品有无限个,物品的重量和价值如下:

重量 价值
物品0 1 15
物品1 3 20
物品2 4 30

问背包能背的物品最大价值是多少?

解题方法

动规五部曲

1.确定dp数组以及下标的含义

使用二维数组,dp[i][j]数组表示从前i个物品中任意取,放进容量为j的背包中所得到的物品的最大价值。

2.递推公式(状态转移方程式)

对于每个物品来说有两种选择,不选取或选取。所以dp[i][j]可以从这两类选择中推导出:

  • 不选取物品i:

    dp[i - 1][j]推出,即背包容量为j,里面不放物品i的最大价值,即dp[i][j] = dp[i - 1][j]

  • 选取物品i:

    **由dp[i][j - weight[i]]推出,注意这里和01背包的区别,因为可以重复放物品i,所以是dp[i][j - weight[i]]**,表示背包容量为j - weight[i]的时候任取物品i的最大价值,那么dp[i][j - weight[i]] + value[i](物品i的价值) ,就是背包放物品i得到的最大价值,即dp[i][j] = dp[i][j - weight[i]] + value[i]

所以,递推公式为:

  • 如果物品i的重量大于背包容量j时,背包放不下,就不能选择物品i,dp[i][j] = dp[i - 1][j]
  • 如果物品i的重量小于等于背包容量j时,dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i]] + value[i])

3.dp数组的初始化

关于初始化,一定要和dp数组的定义一致。

两种初始化情况:

  • 背包容量j为0,不管选择哪些物品,所得到的物品最大价值一定为0,所以dp[i][0] = 0
  • 物品数量为0时,不论背包容量多大,所得到的物品最大价值一定为0,所以dp[0][j] = 0
dp[i][j](物品\背包) 0 1 2 3 4
无物品 0 0 0 0 0
物品0 0
物品1 0
物品2 0

4.dp数组的遍历顺序

有两个遍历的维度:物品和背包,那么问题来了,先遍历物品还是先遍历背包重量呢?

其实都可以,因为递推公式为dp[i][j] = dp[i - 1][j]dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i]] + value[i])这两种情况,不论哪种,dp[i - 1][j]dp[i][j - weight[i]]都在dp[i][j]的左上角方向,而两种遍历顺序都能够获取到dp[i][j]左上角方向的值,先遍历物品会更好理解。

  • 先遍历物品再遍历背包,代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// m为物品的个数,n为背包的容量
int m = weight.length, n = bagWeight;
// m + 1是考虑没有任何物品的情况,n + 1是考虑背包容量为0的情况
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) { // 遍历物品
for (int j = 0; j <= n; j++) { // 遍历背包
if (j < weight[i - 1]) {
dp[i][j] = dp[i - 1][j];
} else {
// 注意这里跟01背包只有下面一个下标不同,那就是“放i”这个选择,因为是可以重复放的,所以是dp[i]
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i - 1]] + value[i - 1]);
}
}
}
  • 先遍历背包再遍历物品,代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// m为物品的个数,n为背包的容量
int m = weight.length, n = bagWeight;
// m + 1是考虑没有任何物品的情况,n + 1是考虑背包容量为0的情况
int[][] dp = new int[m + 1][n + 1];
for (int j = 0; j <= n; j++) { // 遍历背包
for (int i = 1; i <= m; i++) { // 遍历物品
if (j < weight[i - 1]) {
dp[i][j] = dp[i - 1][j];
} else {
// 注意这里跟01背包只有下面一个下标不同,那就是“放i”这个选择,因为是可以重复放的,所以是dp[i]
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i - 1]] + value[i - 1]);
}
}
}

5.打印dp数组

dp数组对应值如下:

dp[i][j](物品\背包) 0 1 2 3 4
无物品 0 0 0 0 0
物品0(重量1,价值15) 0 15 30 45 60
物品1(重量3,价值20) 0 15 30 45 60
物品2(重量4,价值30) 0 15 30 45 60

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// m为物品的个数,n为背包的容量
int m = weight.length, n = bagWeight;
// m + 1是考虑没有任何物品的情况,n + 1是考虑背包容量为0的情况
int[][] dp = new int[m + 1][n + 1];
// dp[i][0]和dp[0][j]情况的初始化省略,因为dp数组的默认值就是0
for (int i = 1; i <= m; i++) { // 遍历物品
for (int j = 0; j <= n; j++) { // 遍历背包
if (j < weight[i - 1]) {
dp[i][j] = dp[i - 1][j];
} else {
// 注意这里跟01背包只有下面一个下标不同,那就是“放i”这个选择,因为是可以重复放的,所以是dp[i]
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i - 1]] + value[i - 1]);
}
}
}
return dp[m][n];

优化为一维dp数组

由于递推公式中dp[i][j]用到了dp[i - 1][j]dp[i][j - weight[i]]即上一层和左边的数据,所以可以将dp[i][j]优化为dp[j]

dp数组以及下标的含义

这里dp[j]数组的表示容量为j的背包中所得到的物品的最大价值。

递推公式(状态转移方程式)

递推公式变为dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i])

dp数组的初始化

dp[0] = 0即可

dp数组的遍历顺序

01背包内嵌的循环是从大到小遍历,为了保证每个物品仅被添加一次;而完全背包的物品是可以添加多次的,所以要从小到大去遍历

1
2
3
4
5
6
7
8
9
// m为物品的个数,n为背包的容量
int m = weight.length, n = bagWeight;
int[] dp = new int[n + 1];
for (int i = 1; i <= m; i++) {
// 注意这里遍历背包顺序又变成了正序,和01背包不同,很重要
for (int j = weight[i - 1]; j <= n; j++) {
dp[j] = Math.max(dp[j], dp[j - weight[i - 1]] + value[i - 1]);
}
}

这里完全背包一维dp数组可以交换遍历顺序吗?

和01背包不同,这里是可以的!因为dp[j]是用到其左边的数据dp[j - weight[i]]的,而先遍历背包再遍历物品也是满足的。

打印dp数组

一维数组完整代码

1
2
3
4
5
6
7
8
9
10
// m为物品的个数,n为背包的容量
int m = weight.length, n = bagWeight;
int[] dp = new int[n + 1];
for (int i = 1; i <= m; i++) {
// 注意这里遍历背包顺序又变成了正序,和01背包不同,很重要
for (int j = weight[i - 1]; j <= n; j++) {
dp[j] = Math.max(dp[j], dp[j - weight[i - 1]] + value[i - 1]);
}
}
return dp[n];
作者

chengzhy

发布于

2022-04-11

更新于

2022-04-14

许可协议

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×