题目描述
blablabla
样例
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例:
10
算法1
(暴力枚举) $O(n^3)$
状态表示f[i,j]:
集合:只考虑所有前i个物品,且总体积不大于j的所有选法。
属性:max;
状态计算(集合的划分)
f[i,j],划分成第i个物品取几件0,1,2,3,…k-1,k;
f[i,j]=max(f[i-1,j],f[i-1,j-v]+w,f[i-1,j-2v]+2w,....f[i-1,j-kv]+kw);
一般式:f[i-1,j-kv]+kw;
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
int v[1010];
int w[1010];
int f[1010][1010];
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=0;j<=m;j++)
{
f[i][j]=f[i-1][j];
for(int k=0;k*v[i]<=j;k++)
{
f[i][j]= max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
}
}
/*也可
for(int j=0;j<=m;j++)
{
for(int k=0;k*v[i]<=j;k++)
{
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);//因为k=0,就包含了f[i-1,j];
}
}
*/
}
printf("%d\n",f[n][m]);
return 0;
}
算法2
(优化) $O(n^2)$
f[i,j]=max(f[i-1,j],f[i-1,j-v]+w,f[i-1,j-2v]+2w,f[i-1,j-3v]+3w,…f[i-1,j-kv]+kw);
f[i,j-v]=max( f[i-1,j-v] ,f[i-1,j-2v]+w ,f[i-1,j-3w]+2w,…f[i-1,j-kv]+(k-1)w);
所以:f[i,j]=max(f[i-1,j],f[i,j-v]+w);
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
int v[1010];
int w[1010];
int f[1010][1010];
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=0;j<=m;j++)
{
f[i][j]=f[i-1][j];//如果这行注释掉那么就过不了,貌似因为就j<v[i]没有被计算
if(j>=v[i])
f[i][j]= max(f[i][j],f[i][j-v[i]]+w[i]);
}
}
printf("%d\n",f[n][m]);
return 0;
}
算法3
(优化成一维)
#include<bits/stdc++.h>
using namespace std;
int n,m;
int v[1010];
int w[1010];
int f[1010];
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=v[i];j<=m;j++)
{
f[j]= max(f[j],f[j-v[i]]+w[i]);
//f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
}
}
printf("%d\n",f[m]);
return 0;
}