动态规划三个重要性质:
- 最优子结构
- 重叠子问题
- 无后效性(在构造解空间时一定要考虑)
一. 0/1背包
问题描述
01背包:有n种物品与承重为m的背包。每种物品只有一件,每个物品都有对应的重量weight[i]与价值value[i],最大化背包价值。
对于背包问题,常见的做法是构建二维数组来构造最优解。以背包问题来说,我们的目标是通过每个物品价值value[i]和重量weight[i],来最大化背包价值,而背包容量实际上则是优化条件。
形式化定义:设dp[i][j]为背包价值函数,dp[i][j]表示在“背包的重量为j时,取前i件物品,所能达到的最大价值”。
对于物品i,此时我们的背包有两种状态,选或不选:
- 如果选择物品i装入背包,则需要背包留出weight[i]的重量来容纳物品i,那么若想让dp[i][j]最大,则只需让dp[i-1][j-weight[i]]最大(即前i-1件物品,使得背包容量为j-weight[i]时价值最大);
- 如果不选择物品i装入背包,则显然dp[i-1][j]最大,便能使得dp[i][j]最大化;
于是得到了0/1背包问题的状态转移方程:
dp[i][j]=max{d[i-1][j], dp[i-1][j-weight[i]]+value[i]}
int zeroOneBackpack(int value[], int weight[], int items, int volume) {
/**
* 0-1背包,二维数组实现
* */
int dp[items + 1][volume + 1];
for (int i = 1; i <= items; ++i) {
for (int j = 1; j <= volume; ++j) {
if (weight[i] > j)
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
return dp[items][volume];
}
采用二维数组实现的方式比较直观,但是内存消耗比较大,如果数据量稍微大一点,估计就爆内存了。于是产生了一种叫“滚动数组”的方式。
滚动数组的思想是因为二维数组中存储了很多的中间状态,最后有用的状态只有dp[items][:]这一行(也就是dp表的最后一行),滚动数组通过迭代的替换中间状态来构造最优解。通过输出每次dp[j]可以看出,一维数组就是对二维数组中的每次中间结果进行更新,最后保留最后一行。(如果内层循环j是从1开始,那么就影响了“无后效性”,相当于每个物品的数目就不是1了,这样问题就变成了完全背包问题,后续计算的结果会受到影响)
一维数组状态转移方程:
dp[j]=max{d[j], dp[j-weight[i]]+value[i]}
int zeroOneBackpack_one_diem(int value[], int weight[], int items, int volume) {
/**
* 0-1背包,滚动数组实现
* */
int dp[volume + 1];
for (int i = 1; i <= items; i++) {
for (int j = volume; j >= weight[i]; j--) {
// 内存循环如果反了就变成完全背包了
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
return dp[volume];
}
打印每轮dp[]结果如下:
当i = 1 : 2 2 2 2 2 2 2 2 2 2 2 2
当i = 2 : 2 2 5 7 7 7 7 7 7 7 7 7
当i = 3 : 2 3 5 7 8 10 10 10 10 10 10 10
当i = 4 : 2 3 5 7 8 10 12 13 15 17 18 20
当i = 5 : 2 4 6 7 9 11 12 14 16 17 19 21
二. 完全背包
问题描述
完全背包:有n种物品与承重为m的背包。每种物品有无限多件,每个物品都有对应的重量weight[i]与价值value[i],最大化背包价值。
根据问题描述,背包能装多少就装多少,既一件物品可以放入背包中k个。
那么,可以得到完全背包的转移方程:
dp[i][j] = max{dp[I][j], dp[i-1][j - k * weight[i]] + k * value[i]}, 0 <= k*weight[i] <= j
int completelyPackage(int value[], int weight[], int items, int volume) {
/**
* 完全背包,二维数组实现
* 能装多少就装多少
* */
int dp[items + 1][volume + 1];
for (int i = 1; i <= items; ++i) {
for (int j = 1; j <= volume; j++) {
for (int k = 1; k * weight[i] <= j; k++) {
if (dp[i - 1][j - k * weight[i]] + k * value[i] > dp[i][j])
dp[i][j] = dp[i - 1][j - k * weight[i]] + k * value[i];
}
}
}
return dp[items][volume];
}
同样为了避免二维数组内存开销大的问题,采用一维数组求解方式类似0/1背包
一维数组状态转移方程:
dp[j]=max{dp[j], dp[j-weight[i]]+value[i]}
int completelyPackage_one_diem(int value[], int weight[], int items, int volume) {
/***
* 完全背包,滚动数组实现
*/
int dp[volume + 1];
for (int i = 1; i <= items; ++i) {
for (int j = weight[i]; j <= volume; ++j) {
if (dp[j - weight[i]] + value[i] > dp[j])
dp[j] = dp[j - weight[i]] + value[i];
}
}
return dp[volume];
}
三. 多重背包
问题描述
多重背包:有n种物品与承重为m的背包。每种物品有有限件num[i],每个物品都有对应的重量weight[i]与价值value[i],最大化背包价值。
多重背包多了一个限制条件,那就是每个物品数量为num[i]件;
那么这个问题完全可以当成是0/1背包问题,也就是将相同的num[i]件物品i看成价值跟重量相同的num[i]件不同的物品。
于是利用0/1背包的思路,得到状态转移方程:
dp[j]=max{dp[j], dp[j-weight[i]]+value[I]}
int multiplePack(int value[], int weight[], int num[], int items, int volume) {
int dp[volume + 1];
for (int i = 1; i <= items; i++) {
for (int k = 0; k < num[i]; k++) {
for (int j = volume; j >= weight[i]; j--) {
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
}
return dp[volume];
}