二维dp
状态表示:f[i][j]:选择前i件商品时,体积不超过j时,最大的商品价值
状态计算:
1. 不选择第i件商品:f[ i ][ j ]=f[ i-1 ][ j ]
2. 选择第i件商品; f[ i ][ j ]=f[ i-1 ][ j-v[i] ]+v[ i ]*w[ i ];
(前提条件: v[ i ]<j 即第i件商品的体积小于总体积)
#include <iostream>
using namespace std;
const int N=3e4+10,M=30;
int f[M][N];
int v[M],w[M];
int n,m;
int main()
{
cin>>m>>n;//m是总价钱,n是总个数
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
{ f[i][j]=f[i-1][j];
if(v[i]<=j)//第i件物品的体积也能放入总体积j中
f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]*v[i]);
}
cout<<f[n][m]<<endl;
return 0;
}
一维优化:
f[ j ]=max( f[ j ] , f[ j-v[ i ] ] + w * v)
#include <iostream>
#include <algorithm>
using namespace std;
const int N=3e4+10;
int f[N];
int m,n;
int main()
{
cin>>m>>n;//n表示商品个数,m表示总价钱
for(int i=1;i<=n;i++)
{
int v,w;
cin>>v>>w;
for(int j=m;j>=v;j--)//体积从大到小枚举
f[j]=max(f[j],f[j-v]+w*v);
}
cout<<f[m]<<endl;
return 0;
}
Note: 为什么体积要从大到小枚举:
for(int j=m;j>=v;j--)//体积从大到小枚举
f[j]=max(f[j],f[j-v]+w*v);
j-v[i]一定严格小于v[i],由于程序采用递归的形式,要求保证f[j-v[i]]没有出现过,所以要将j从大到小枚举