C++ 代码
算法一
#include<iostream>
#include<algorithm>
using namespace std;
const int M=1e3+10;
int N,V;
int w[M],v[M];
int f[M][M];
int main()
{
scanf("%d%d",&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++)
{
if(j<v[i])
f[i][j]=f[i-1][j];
else
f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]);
}
}
printf("%d",f[N][V]);
}
优化过后
#include<iostream>
#include<algorithm>
using namespace std;
const int M=1e3+10;
int N,V;
int w[M],v[M];
int f[M];
int main()
{
scanf("%d%d",&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]);
}
printf("%d",f[V]);
}