<—点个赞吧QwQ

宣传一下算法基础课整理

有 $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

输出样例：

8

思路1

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

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

状态计算：

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

代码1

#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 - 1][j - w] + v);
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

思路2

由于只用到了上一层的信息，所以可以滚动数组优化。

代码2

#include <iostream>
using namespace std;
const int N = 1010;
int n,m;
int f[2][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) & 1][j - w] + v);
        }
    }
    cout << f[n & 1][m] << endl;
    return 0;
}

思路3

这里我们用的上一层信息，如果要用的话，可以自动复制下来（因为是一维数组，所以上一层的计算结果就保存在同一行），但是由于正着循环会把前面$i-1$层的数据覆盖掉，所以要采用倒叙循环。
如果正序循环，$f_i$可能$=f_{i-2\times w_i}+2 \times v_i$，就不满足了$0/1$背包只能取一次的要求。

代码3

#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 = m;j >= w;j--) f[j] = max (f[j],f[j - w] + v);
    }
    cout << f[m] << endl;
    return 0;
}