···
include[HTML_REMOVED]
using namespace std;
const int N=1010;
int v[N],w[N],f[N];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i) cin>>v[i]>>w[i];
for(int i=1;i<=n;i)//i表示从前几个背包中选择。
for(int j=m;j>=v[i];j–)//j表示背包的体积。
f[j]=max(f[j],f[j-v[i]]+w[i]);
cout<<f[m];
return 0;
}//eg:i=1时,f[5]就表示从前一件物品中选择体积不超过5的能装的最大价值。所以f[5]=2,f[4]=2,f[3]=2,f[2]=2,f[1]=2;
//i=2时,f[5]就表示从前两件物品中选择体积不超过5的能装的最大价值。f[5]=6,f[4]=6,f[3]=6,f[2]=4,f[1]=2;
//i从1到n不断更新最终所得的就是在体积不超过m的情况下所能装的最大价值。
···