C++ 代码

/*
状态属性:f[i][j],表示前i个物品，容量为j的总价值数
状态计算：
    第i个物品选0次,f[i][j]=f[i-1][j];
    第i个物品选1次,f[i][j]=f[i-1][j-v[i]]+w[i];
    第i个物品选2次,f[i][j]=f[i-1][j-2*v[i]]+2*w[i];
    第i个物品选3次,f[i][j]=f[i-1][j-3*v[i]]+3*w[i];
    ...
    第i个物品选k次,f[i][j]=f[i-1][j-k*v[i]]+k*w[i];
写成一排来看看：f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i],f[i-1][j-2*v[i]]+2*w[i],f[i-1][j-3*v[i]]+3*w[i]
                ,...f[i-1][j-k*v[i]]+k*w[i])等价于
                f[i][j]=max(f[i-1][j],max(f[i-1][j-v[i]],f[i-1][j-2*v[i]]+ *w[i],f[i-1][j-3*v[i]]+2*w[i]
                ,...f[i-1][j-k*v[i]]+(k-1)*w[i])+w[i])
    我们使用换元法，来看看：f[i][j]=max(f[i-1][j-v[i]],f[i-1][j-2*v[i]]+1 *w[i],f[i-1][j-3*v[i]]+2*w[i]
                ,...f[i-1][j-k*v[i]]+(k-1)*w[i])+w[i]中间的这一坨，使用j-v[i]来进行换元
                f[i][j-v[i]]=max(f[i][j-2*v[i]],f[i][j-3*v[i]]+1*w[i],...)+w[i]发现规律没，上面的那一坨可以替换成
                f[i][j]=max(f[i-1][j-v[i]]+w[i],max(f[i-1][j-2*v[i]]+1 *w[i],f[i-1][j-3*v[i]]+2*w[i]
                ,...f[i-1][j-k*v[i]]+(k-1)*w[i])+w[i])--->在进行提取
                f[i][j]=max(f[i-1][j-v[i]]+w[i],max(f[i-1][j-2*v[i]],f[i-1][j-3*v[i]]+1*w[i]
                ,...f[i-1][j-k*v[i]]+(k-2)*w[i])+w[i]+w[i])--->第二个max是不是等于f[i][j-v[i]]+w[i],那么此时
                f[i][j]=max(f[i-1][j-v[i]]+w[i],f[i][j-v[i]]+w[i])---->

最后的值为max(上述的max);--->
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i],f[i][j-v[i]]+w[i])
*/

#include<iostream>
#include<vector>
using namespace std;

int main(){
    int N,V;
    cin>>N>>V;
    vector<vector<int>> dp(N+1,vector<int>(V+1,0));
    vector<int> vs(N+1,0),ws(N+1,0);
    for(int i=1;i<=N;i++){
        cin>>vs[i]>>ws[i];
    }
    for(int i=1;i<=N;i++){
        for(int j=0;j<=V;j++){
            dp[i][j]=dp[i-1][j];
            if(j>=vs[i]){
                dp[i][j]=max(max(dp[i][j],dp[i-1][j-vs[i]]+ws[i]),dp[i][j-vs[i]]+ws[i]);
            }
        }
    }
    cout<< dp[N][V]<<endl;
    return 0;
}