f[i][j] 定义：在前 i 个物品当中选择，在总体积不超过 j 的情况下的最大价值
考虑与 01 背包相同的处理方式，对第 i 个物品的选择次数做划分，有：
-
选择 0 次：f[i−1][j]
-
选择 1 次：f[i−1][j−v]+w
-
选择两次：f[i−1][j−2v]+2w
-
选择 s 次：f[i−1][j−sv]+sw （这里的 s 次表示在背包体积为 j 下，第 i 个物品的最大选择次数）
即：f[i][j]=max(f[i−1][j],f[i−1][j−v]+w,f[i−1][j−2v]+2w,…,f[i−1][j−sv]+sw)
我们往后写一位，有：f[i][j−v]=max(f[i−1][j−v],f[i−1][j−2v]+w,f[i−1][j−3v]+2w,…,f[i−1][j−sv]+(s−1)w)
为什么最后一项是 f[i−1][j−sv]+(s−1)w ?
这是因为在体积为 j 的条件下，物品 i 最大的选择次数只能到 s 次，那么在体积为 j−v 的条件下，物品 i 只能选择 s−1 次，这正好对应后面是加上 (s−1)w
对比上面两个式子，不难发现有颜色的部分都是相同的，只是差一个偏移量
因此我们有：f[i][j]=max(f[i−1][j],f[i][j−v]+w)
完整代码：
#include <iostream>
using namespace std;
const int N = 1010;
int v[N], w[N];
int f[N][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++)
for(int j = 1; j <= m; j++)
{
f[i][j] = f[i - 1][j];
if(j - v[i] >= 0) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
}
cout << f[n][m] << endl;
return 0;
}
因为这里只使用了第 i 层和第 i−1 层，同样可以考虑空间优化
由于对 f[i][j] 的更新需要使用上一层 j 出的值以及本层 j−v[i] 处的值，前者是未更新的，后者是已更新的
因此我们可以直接从前往后遍历，这样当我们要对 f[j] 进行赋值时，原先的值可以表示 f[i−1][j] ，而 f[j−v[i]] 是本层已经更新的值
所以我们直接从前往后遍历即可
完整代码：
#include <iostream>
using namespace std;
const int N = 1010;
int v[N], w[N];
int 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++)
for(int j = v[i]; j <= m; j++)
{
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
cout << f[m] << endl;
return 0;
}
