<—点个赞吧QwQ

宣传一下算法基础课整理{:target=”_blank”}

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

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

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

输入格式

第一行两个整数，$N，V$，用空格隔开，分别表示物品种数和背包容积。

接下来有 $N$ 行，每行两个整数 $v_i, w_i$，用空格隔开，分别表示第 $i$ 种物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

$0 \\lt N, V \\le 1000$
$0 \\lt v_i, w_i \\le 1000$

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

10

思路1

闫氏$\text{DP}$分析法：
状态表示：$f_{i,j}$

• 集合：只从前$i$个物品选，总体积不超过$j$的方案集合
• 属性：$\max$

状态计算：

• 如果不选，那么最大价值就是前$i-1$个物品的最大价值，即$f_{i-1,j}$
• 如果选$1$个，那么最大价值就是$f_{i-1,j-w}+v$
• 如果选$2$个，那么最大价值就是$f_{i-1,j-2\times w}+2\times v$
• 如果选$k$个，那么最大价值就是$f_{i-1,j-k\times w}+k\times v$
• 所以状态转移方程就是$f_{i,j}=\underset{0\le k\times w \le j}\max\lbrace f_{i-1,j-k\times w}+k \times v_i\rbrace$

代码1

#include <iostream>
using namespace std;
const int N = 1010,M = 1010;
int n,m;
int f[N][M];
int main () {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        int w,v;
        cin >> w >> v;
        for (int j = 0;j <= m;j++) {
            for (int k = 0;k * w <= j;k++) f[i][j] = max (f[i][j],f[i - 1][j - k * w] + k * v);
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

思路2

大家可以发现上一份代码一下就超时了，这里我们需要优化：
先对比一下两个式子：
$f_{i,j}~~~~=\max\lbrace f_{i-1,j},f_{i-1,j-w} + v,f_{i-1,j-2\times w}+2\times v…\rbrace$
$f_{i,j-w}=\max\lbrace~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~f_{i-1,j-w},f_{i-1,j-2\times w}+v…\rbrace$
大家可以发现，$f_{i,j-w}+v$涵盖了$f_{i,j}$中除$f_{i-1,j}$之外的所有项，所以新的状态转移方程就是：

• $f_{i,j}=\max\lbrace f_{i-1,j},f[i][j-w]+v\rbrace$

代码2

#include <iostream>
using namespace std;
const int N = 1010;
int n,m;
int f[N][N];
int main () {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        int w,v;
        cin >> w >> v;
        for (int j = 0;j <= m;j++) {
            f[i][j] = f[i - 1][j];
            if (j >= w) f[i][j] = max (f[i][j],f[i][j - w] + v);
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

思路3

由于只用到当前层和上一层的数据，我们可以进一步用滚动数组优化。

代码3

#include <iostream>
using namespace std;
const int N = 1010;
int n,m;
int f[N][N];
int main () {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        int w,v;
        cin >> w >> v;
        for (int j = 0;j <= m;j++) {
            f[i & 1][j] = f[(i - 1) & 1][j];
            if (j >= w) f[i & 1][j] = max (f[i & 1][j],f[i & 1][j - w] + v);
        }
    }
    cout << f[n & 1][m] << endl;
    return 0;
}

思路4

这里可以用跟$0/1$背包最后类似的方法进行优化。
我们直接用一维数组，而这里要正序循环，因为正着循环刚刚好能满足完全背包每个物品有无限个的要求。

代码4

#include <iostream>
using namespace std;
const int M = 1010;
int n,m;
int f[M];
int main () {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        int w,v;
        cin >> w >> v;
        for (int j = w;j <= m;j++) f[j] = max (f[j],f[j - w] + v);
    }
    cout << f[m] << endl;
    return 0;
}