0/1背包问题
炎拳镇楼
预备知识
1 什么是动态规划(DP)
动态规划问题实质上就是把一个复杂的问题分解为很多简单子问题在加以解决的方法。非常符合道家一生二二生三三生万物的思想,优秀的系统的底层实现一定是十分简单。将一个问题实时拆分成简单的问题并加以解决,最后得到正确答案,这便是我堆动态规划问题的理解。
2 状态和状态转移方程
- 状态: 即描述一个问题需要的变量 。例如,一辆汽车行驶的距离问题,则我们描述它的状态可以是 速度和时间 ,也可以是加速度和时间等等。状态根据问题的不同,其个数和形式是不一样的。例如本题,其状态可以 背包的空间和所选物品
- 状态转移方程:状态转移:同自动控制原理类似,状态的转移就是状态的变化,状态转移方程在程序上就是如何利用算法实现对状态变量的更新。如小车路程问题,我们选择状态变量是速度和时间,那么状态转移方程就是速度和时间的更新。 本例题,状态的转移方程就是如何去更新 背包的空间和所选物品的品类
3 动态规划问题上关于状态的考虑
直接上图:
动态规发问题可以一定程度上想成图论中的搜索问题 ,状态就相当于节点,而状态转移就是从一个节点指向另外一个节点。
算法原理
结合上诉预备知识,本道题我们可以总结出以下几点:
- 1. 状态:(i , j) i:表示前i见物品 , j:表示总看见不超过 j
- 2. 状态属性:f(i , j):前i件物品不超过j容量下的最大价值
- 3. 状态如何计算:可以将f(i , j)分为两部分,一部分是不含第i个物件的部分,另外一部分是含第i个物件的部分。则(i , j)可分为如图的两部分
那么结合算法原理,二维状态的核心代码如下:
for(i:遍历所有物品){
for(j:0 - 最大容量){
if(装不下第i个物品) f(i , j) = f(i - 1, j);//对用不含第i个物件的集合
esle f(i , j ) = max{f[i - 1][j] , f[i - 1][j - v[i]] + 第i件物品的价值}
}
}
关于含第i见物品的集合,需要转换成:f(i - 1,j - v[i]) w[i]即从前i-1件物品中选择 不超过 j - v[i]的体积的物品 再加上必选的第i件物品的价值
二维状态的代码如下
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n , m;//物体数量 背包容量
int v[N] , w[N];//v[i]:表示第i件体积 w[]:表示第i件价值
int f[N][N];//状态
void show(){
for(int i = 1 ; i <= 4; i++){
for(int j = 0; j <= 5; j++){
printf("%d " , f[i][j]);
}
printf("\n");
}
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n ; i++) cin >> v[i] >> w[i];//注意从下标1开始
for(int i = 1; i <= n; i++){//枚举每件物品及其体积,得到状态
for(int j = 1; j <= m; j++){
if(j < v[i]) f[i][j] = f[i - 1][j];//集合划分中的第一种情况:不含第i见物品
else f[i][j] = max(f[i -1][j] , f[i -1][j - v[i]] + w[i]);//注意 第二种含i的集合必须在总体积小于当前j的情况才存在!
}
show();
printf("\n");
}
cout << f[n][m] << endl;//输出最后结果即可
return 0;
}
一维状态求解
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n , m;//物体数量 背包容量
int v[N] , w[N];//v[i]:表示第i件体积 w[]:表示第i件价值
int f[N];//压缩成一维状态
int main(){
cin >> n >> m;
for(int i = 1; i <= n ; i++) cin >> v[i] >> w[i];//注意从下标1开始
for(int i = 1; i <= n; i++){//枚举每件物品及其体积,得到状态
for(int j = m; j >= v[i]; j--){//由于j - v[i]一定严格小于j,所以从j = v[i]开始
//删掉了i这一维变成了 f[j] = f[j] ,所以直接删掉
f[j] = max(f[j] , f[j - v[i]] + w[i]);
}
}
cout << f[m] << endl;//输出最后结果即可
return 0;
}
状态压缩
首先我们先打印每轮f[i][j]内部值的大小并标注一下状态到底和哪些值比较后更新的
图中的红蓝线均表示状态从上一个i- 1到这次i中和哪些状态进行对比了并更新
我们不难发现以下2个规律:
- 1. 对于第i
次更新,它仅与i - 1
次的状态和w[i]
有关,和i -1
之前的状态无关。
- 2. 对于第i
次更新,前j - v[i] <= 0
次的状态没用更新(详细看图中蓝线),因为(i , j)的极限容量是 j, 所以在v[i] > j之前,状态都不会更新,也更新不了。
详细看看代码:
for(int i = 1; i <= n; i++){//枚举每件物品及其体积,得到状态
for(int j = 1; j <= m; j++){
if(j < v[i]) f[i][j] = f[i - 1][j];//集合划分中的第一种情况:不含第i见物品
else f[i][j] = max(f[i -1][j] , f[i -1][j - v[i]] + w[i]);//注意 第二种含i的集合必须在总体积小于当前j的情况才存在!
}
printf("\n");
}
if(j < v[i]) f[i][j] = f[i - 1][j];
结合规律1.我们可以直接不需要i
来进行更新,这便使得代码变成了f[j] = f[j]
,恒等式直接删掉,即我们发现不需要更新j < v[i]
的状态,这也是符合规律2.。for(int j = 1; j <= m; j++)
因为j < v[i]
是不更新的,所以循环的次数也可以改为j >= v[i]
后。即for(int j = v[i]; j <= m; j++)
- 接下来,我们便要修改后续代码的内容
f[i][j] = max(f[i -1][j] , f[i -1][j - v[i]] + w[i])
假如直接删去i - 1
和i
,则代码变成如下的样子
for(int i = 1; i <= n; i++){//枚举每件物品及其体积,得到状态
for(int j = v[i]; j <= m; j++){//由于j - v[i]一定严格小于j,所以从j = v[i]开始
//删掉了i这一维变成了 f[j] = f[j] ,所以直接删掉
f[j] = max(f[j] , f[j - v[i]] + w[i]);
}
}
输出的结果和状态更新如下图
- 只会更新蓝线前面的数据
- 由图便可以看出问题,由于状态被压缩,f[]数组变成了一维,在j = 0 ~ m
递增的情况下,状态更新的方法是错误的,对比第一组的绿线和二维的第一次更新路线可以看出 从j = 2
的f[1][j]开始错误的使用了本该在i = 2
f[2][j]的状态进行更新。所以接下的数据便全乱了!
- 正确的更新方式是j
逆序更新,即j = m -> v[i]
进行更新 代码如下
for(int i = 1; i <= n; i++){//枚举每件物品及其体积,得到状态
for(int j = m; j >= v[i]; j--){//由于j - v[i]一定严格小于j,所以从j = v[i]开始
//删掉了i这一维变成了 f[j] = f[j] ,所以直接删掉
f[j] = max(f[j] , f[j - v[i]] + w[i]);
}
}
正确的更新流程如下图所示