动态规划————要想达到最终状态,就要利用之前的状态。
样例描述
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例:
8
对应物品编号的体积与价值表:
i | v( i ) | w( i ) |
---|---|---|
1 | 1 | 2 |
2 | 2 | 4 |
3 | 3 | 4 |
4 | 4 | 5 |
( i是物品编号,v ( i ) 是物品体积,w ( i ) 是物品价值,j 是背包容量)
f ( i , j ) 是从 1 ~ i 个物品中选并且这些物品总体积不能超过j的价值最大的选法
f ( i , j )表:
i \ j | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 2 | 2 | 2 | 2 | 2 |
2 | 0 | 2 | 4 | 6 | 6 | 6 |
3 | 0 | 2 | 4 | 6 | 6 | 8 |
4 | 0 | 2 | 4 | 6 | 6 | 8 |
f ( i , j ) = max ( f ( i - 1 , j ) , f ( i - 1 , j - v ( i ) ) + w ( i ) ),
① f ( i - 1 , j ) 代表不把第i个物品选上,只选择 1 ~ i - 1 个物品的选择并且总体积不超过 j ,
② f ( i - 1 , j - v ( i ) + w ( i ) 代表选上第i个物品,但不能直接在 f ( i - 1 , j ) 上加,还要保证总体积
不超过 j - v ( i )。
f ( i , j ) 在①②两种情况中选价值最大的。
例如 f ( 3 , 3 ) 选的是第 1 件和第 2 件物品 f ( 3 , 3 ) = f ( 2 , 3 ) = 6 ; f ( 3 , 5 ) 选的是第 2 件和第 3 件物品 f ( 3 , 3 ) = f ( 2 , 5 - 3 ) + 4 = 8
代码
include<cstdio>
#include<cmath>
using namespace std;
const int N=1010;
int v[N],w[N];//v[1~n]代表1~n物品的体积,w[1~n]代表1~n的价值
int f[N][N];//f[0][0~n]=0,f[0~n][0]=0 (全局变量默认都为0)
int n,m;//分别代表物品种数,背包总体积
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d%d",&v[i],&w[i]);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
if(j-v[i]>=0) f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
else f[i][j]=f[i-1][j];
}
printf("%d",f[n][m]);
return 0;
}
优化
由于 f ( i , j ) = max ( f ( i - 1 , j ) , f ( i - 1, j -v ( i ) ) + w ( i ) ) ,
f ( i , j ) 都是由 i - 1 层决定的,因此可以考虑一层一层的覆盖,使 f ( i , j ) 简化成 f ( j ) ,变成
f ( j ) = max ( f ( j ) , f ( j - v ( i ) ) + w ( i ) ) 。
下面看循环条件还是 i 从 1 ~ n ,j 从 1 ~ m 的举例,
初始化:当 i = 0 时, f ( 0 ~ m ) = 0
0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 |
i = 1 时,f ( 1 ~ m ) :
f ( 1 ) = max ( f ( 1 ) , f ( 1 - 1 ) + 2 ) = max ( 0 , 0 + 2 ) = 2 ;
f ( 2 ) = max ( f ( 2 ) , f ( 2 - 1 ) + 2 ) = max ( 0 , 2 + 2 ) = 4 ;
0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
0 | 2 | 4 |
对比二维,f ( 2 ) 应该等于 2 才对,在二维中 f ( 1 , 2 ) 比较的应该是 f ( 0 , 2 ) 和 f ( 0 , 2 - 1 )即f ( 0 , 1 ) 的结果,而这里 f ( 2 ) 右边的 f ( 1 ) 不再是上一层的结果,而是刚刚算出的 f ( 1 ) 覆盖了,属于第i层的结果了。
因此为了避免用上层结果时,被这层结果覆盖的情况,
将 j 变为从 m ~ 1 ,同时将 j > = v ( i ) 的条件提上来,变成 j 从 m ~ v ( i )
下面看循环条件还是 i 从 1 ~ n ,j 从 m ~ v ( i )的举例,
初始化:当 i = 0 时,f ( 0 ~ m ) = 0
0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 |
i = 1 时, f ( m ~ v( 1 ) ) :
f ( 5 ) = max ( f ( 5 ) , f ( 5 - 1 ) + 2 ) = max ( 0 , 0 + 2 ) = 2 ;
f ( 4 ) = max ( f ( 4 ) , f ( 4 - 1 ) + 2 ) = max ( 0 , 0 + 2 ) = 2 ;
f ( 3 ) = max ( f ( 3 ) , f ( 3 - 1 ) + 2 ) = max ( 0 , 0 + 2 ) = 2 ;
f ( 2 ) = max ( f ( 2 ) , f ( 2 - 1 ) + 2 ) = max ( 0 , 0 + 2 ) = 2 ;
f ( 1 ) = max ( f ( 1 ) , f ( 1 - 1 ) + 2 ) = max ( 0 , 0 + 2 ) = 2 ;
更新 f ( j ) :
0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
0 | 2 | 2 | 2 | 2 | 2 |
i = 2 时 , f ( m ~ v ( 2 ) ) :
f ( 5 ) = max ( f ( 5 ) , f ( 5 - 2 ) + 4 ) = max ( 2 , 2 + 4 ) = 6 ;
f ( 4 ) = max ( f ( 4 ) , f ( 4 - 2 ) + 4 ) = max ( 2 , 2 + 4 ) = 6 ;
f ( 3 ) = max ( f ( 3 ) , f ( 3 - 2 ) + 4 ) = max ( 2 , 2 + 4 ) = 6 ;
f ( 2 ) = max ( f ( 2 ) , f ( 2 - 2 ) + 4 ) = max ( 2 , 0 + 4 ) = 4 ;
更新 f ( j ) :
0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
0 | 2 | 4 | 6 | 6 | 6 |
i = 3 时,f ( m ~ v ( 3 ) ) :
f ( 5 ) = max ( f ( 5 ) , f ( 5 - 3 ) + 4 ) = max ( 6 , 4 + 4) = 8 ;
f ( 4 ) = max ( f ( 4 ) , f ( 4 - 3 ) + 4 ) = max ( 6 , 2 + 4) = 6 ;
f ( 3 ) = max ( f ( 3 ) , f ( 3 - 3 ) + 4 ) = max ( 6 , 0 + 4) = 6 ;
更新 f ( j ) :
0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
0 | 2 | 4 | 6 | 6 | 8 |
i = 4 时 , f ( m ~ v ( 4 ) ) :
f ( 5 ) = max ( f ( 5 ) , f ( 5 - 4 ) + 5 ) = max ( 8 , 2 + 5) = 8 ;
f ( 4 ) = max ( f ( 4 ) , f ( 4 - 4 ) + 5 ) = max ( 6 , 0 + 5) = 6 ;
更新 f ( j ) :
0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
0 | 2 | 4 | 6 | 6 | 8 |
最后 f ( j ) 结果与二维的 f ( 4 , j ) 结果一样,说明正确。
代码
include<cstdio>
#include<cmath>
using namespace std;
const int N=1010;
int v[N],w[N];//v[1~n]代表1~n物品的体积,w[1~n]代表1~n的价值
int f[N];//f[0~n]=0
int n,m;//分别代表物品种数,背包总体积
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d%d",&v[i],&w[i]);
for(int i=1;i<=n;i++){
for(int j=m;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
printf("%d",f[m]);
return 0;
}