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

结论： $f[i][j]=\max(f[i-1][j],f[i-1][j-v[i]]+w[i])$

思路：

• $1. 状态表示$
  $集合：从前\ i\ 个物品中选，体积不超过\ j\ 的价值$
  $属性：\max$

• $2. 状态转移$
  $不选第\ i\ 个物品：f[i-1][j]$
  $选择第\ i\ 个物品：f[i-1][j-v[i]]+w[i]$

• $3. 滚动数组$
  $由于\ f[i][j]\ 只需用到当前层和上一层，则结论可转化为：f[j]=\max(f[j],\ f[j-v[i]]+w[i])$

完整代码1（二维）

#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++)
        {
            f[i][j]=f[i-1][j]; //不选第 i 个物品
            if(j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]); //选第 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]; //体积不超过 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=m;j>=v[i];j--) //保证了 f[j-v[i]] 是 f[i-1][j-v[i]]
            f[j]=max(f[j],f[j-v[i]]+w[i]); //f[i][j]=max(f[i-1][j], f[i-1][j-v[i]]+w[i])

    cout<<f[m]<<endl; //体积不超过 m 的最大价值

    return 0;
}