这道题的思考方式与01背包问题一样开二维就好
定义出发版
f[i][j]= max(f[i][j],f[i-1][j-v[i]k]+w[i]k)
时间复杂度太高,导致他
过不了
#include <iostream>
using namespace std;
const int N=1E3+10;
int v[N],w[N];
int n,m;
int f[N][N];
int main()
{
cin>>n>>m;
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++)//容量
for(int k=0;k*v[i]<=j;k++)//第i个物品取几个
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+w[i]*k);
cout<<f[n][m];
return 0;
}
优化后1版
从f[i][j]=f[i-1][j-v[i]k]+kw[i]入手
f[i][j]可以化简为max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-v2]+w2 ···)
f[i][j-v]可以化简为max(f[i-1][j-v],f[i-1][j-2v]+w,f[i-1][j-3v]+2w···)
所以f[i][j]化简后除了f[i-1][j],其他的都是f[i][j-v]+w
所以f[i][j]=max(f[i-1][j],f[i][j-v]+w);
这样就可以减少一层循环,时间复杂度也减小了
#include <iostream>
using namespace std;
const int N=1010;
int v[N],w[N];
int n,m;
int f[N][N];
int main()
{
cin>>n>>m;
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(j>=v[i]) f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
}
cout<<f[n][m];
return 0;
}
优化后2版
观察上一个代码,是不是觉得和01背包代码很像?
我们可以用01的方式把1版再次优化,变为1维
#include <iostream>
using namespace std;
const int N=1010;
int v[N],w[N];
int n,m;
int f[N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>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]);
cout<<f[m];
return 0;
}