$\color{red}{DP}$——目录

题目大意：

有 $N$ 种物品和一个容量是 $V$ 的背包，每种物品都有无限件可用。

第 $i$ 种物品的体积是 $v_i$，价值是 $w_i$。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

解题方法：

完全背包，和01背包问题的差别并不大，只不过是可以有无限件物品而已。
那我们就可以直接枚举每个物品使用的个数，接下来直接套用01背包即可。

$$闫氏DP分析法$$

1. 状态表示——集合：$f[i][j]$ 表示考虑前 $i$ 个物品，且总体积不超过 $j$ 的集合下能获得的最大价值。
2. 状态表示——属性：因为是求最大价值，故为 $max$。
3. 状态计算——集合划分：考虑第 $i$ 个选不选。
   • 不选或选不了（剩余体积不够 $j < v[i]$）：$f[i - 1][j]$。
   • 选：$f[i - 1][j - v[i]] + w[i]$。首先你对第$i$个物品进行了你的抉择，所以前一维变成了$i - 1$，接着因为使用了$v[i]$的体积，所以应该是$j - v[i]$，最后你要把它带来的价值加上，所以要加上$w[i]$。

完整代码，时间复杂度：$O(nm^2)$

#include <iostream>

using namespace std;

const int N = 1100;
int n, m;
int v[N], w[N];
int f[N][N];

int main() {
    int n, m;
    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];
            for (int k = 1; k <= j / v[i]; k ++ ) {
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
            }
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

可惜了，这样的做法会 $\color{red}{TLE}$，所以我们要做一些改变hh
想要变化，先要从公式入手，我们这就来看一看：

我们很快意识到：第一行的每一项都比第二行的对应项多一个 $w$（不包括 $f[i - 1][j]$）。

那么式子经过一通秀操作变成了这样：

f[i][j] = max(f[i - 1][j], f[i][j - v] + w);

其实也可以从字面意思理解，在使用了一个当前物品后，继续考虑当前这个物品。
这样时间复杂度降成了 $O(nm)$，可以 $\color{green}{AC}$

完整代码，时间复杂度：$O(nm)$

#include <iostream>

using namespace std;

const int N = 1100;
int n, m;
int v[N], w[N];
int f[N][N];

int main() {
    int n, m;
    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;
}

知识扩充：

相应的，这道题也可以如同 01 背包问题优化成一维。
但是，这里的循环顺序又要变成正着干了，这就回到了这个东西的定义已经更新。

万物要弄懂他的本质，才能算彻底的理解了他

回到 01 背包问题，我们要看看倒着循环的原因。
因为当你考虑 $f[j]$ 时，$f[j - v]$ 已经被当前物品更新了一次，再从这个位置更新会导致重复选择，所以必须倒着枚举，避免发生冲突

那么现在我们不就是想一个位置重复选择吗（逃
当你现在考虑 $f[j]$，你转移的时候转移的应该是已经被当前物品更新过的，所以必须正着枚举

完整代码，时间复杂度：$O(nm)$

#include <iostream>
#include <cstring>
#include <algorithm>

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]);

    cout << f[m] << endl;
    return 0;
}