$\huge \color{orange}{成仙之路->}$ $\huge \color{purple}{算法基础课题解}$

推导：

$因为\ \ f[i][j]=\max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2v]+2w,…)$

$\ \ \ \ \ \ \ \ \ f[i][j-v]=\max(\ \ \ \ \ \ \ \ \ \ \ \ f[i-1][j-v]\ \ \ \ \ \ \ ,f[i-1][j-2v]+w,…)$

$所以\ \ f[i][j]=\max(f[i-1][j],f[i][j-v]+w)$

完整代码1（TLE了，只过了12/14个数据）

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;

int n,m;
int v[N],w[N];
int f[N][N]; //只从前 i 个物品里面选，体积不超过 j 的最大价值

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=1;j<=m;j++)
            for(int k=0;k*v[i]<=j;k++) //第 i 个物品选 k 个
                f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);

    cout<<f[n][m]<<endl; //只从前 n 个物品里面选，体积不超过 m 的最大价值

    return 0;
}

完整代码2（二维）

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;

int n,m;
int v[N],w[N];
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=1;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]<<endl; 

    return 0;
}

完整代码3（一维）

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;

int n,m;
int v[N],w[N];
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]); // f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i])

    cout<<f[m]<<endl; 

    return 0;
}