思路提示
未优化
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e3+10;
int n,v;
int f[N][N];
int W[N],V[N];
int main()
{
cin>>n>>v;
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<=v;j++)
{
f[i][j]=f[i-1][j];
if(j>=V[i])
//推导一下公式
f[i][j]=max(f[i-1][j],f[i][j-V[i]]+W[i]);
}
cout<<f[n][v];
}
优化后 (与01背包进行对比,区别在于由从大到小,变为从小到大)
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e3+10;
int n,v;
int f[N];
int W[N],V[N];
int main()
{
cin>>n>>v;
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<=v;j++)
{
f[j]=max(f[j],f[j-V[i]]+W[i]);
}
cout<<f[v];
}