<—点个赞吧QwQ

宣传一下算法提高课整理

有 $N$ 件物品和一个容量是 $V$ 的背包，背包能承受的最大重量是 $M$。

每件物品只能用一次。体积是 $v_i$，重量是 $m_i$，价值是 $w_i$。

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

输入格式

第一行三个整数，$N,V, M$，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。

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

输出格式

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

数据范围

$0 \lt N \le 1000$
$0 \lt V, M \le 100$
$0 \lt v_i, m_i \le 100$
$0 \lt w_i \le 1000$

输入样例

4 5 6
1 2 3
2 4 4
3 4 5
4 5 6

输出样例：

8

思路1

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

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

状态计算：

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

代码1

#include <iostream>
using namespace std;
const int N = 110;
int n,m1,m2;
int f[N][N][N];
int main () {
    cin >> n >> m1 >> m2;
    for (int i = 1;i <= n;i++) {
        int w1,w2,v;
        cin >> w1 >> w2 >> v;
        for (int j1 = m1;j1 >= 0;j1--) {
            for (int j2 = m2;j2 >= 0;j2--) {
                f[i][j1][j2] = f[i - 1][j1][j2];
                if (j1 >= w1 && j2 >= w2) f[i][j1][j2] = max (f[i][j1][j2],f[i - 1][j1 - w1][j2 - w2] + v);
            }
        }
    }
    cout << f[n][m1][m2] << endl;
    return 0;
}

思路2

由于只用到了上一面信息（因为是二维），所以可以使用滚动数组优化。

代码2

#include <iostream>
using namespace std;
const int N = 110;
int n,m1,m2;
int f[N][N][N];
int main () {
    cin >> n >> m1 >> m2;
    for (int i = 1;i <= n;i++) {
        int w1,w2,v;
        cin >> w1 >> w2 >> v;
        for (int j1 = m1;j1 >= 0;j1--) {
            for (int j2 = m2;j2 >= 0;j2--) {
                f[i & 1][j1][j2] = f[(i - 1) & 1)][j1][j2];
                if (j1 >= w1 && j2 >= w2) f[i & 1][j1][j2] = max (f[i & 1][j1][j2],f[(i - 1) & 1][j1 - w1][j2 - w2] + v);
            }
        }
    }
    cout << f[n & 1][m1][m2] << endl;
    return 0;
}

思路3

我们可以用类似$0/1$背包的优化思路，直接用二维数组。

代码3

#include <iostream>
using namespace std;
const int N = 110;
int n,m1,m2;
int f[N][N];
int main () {
    cin >> n >> m1 >> m2;
    for (int i = 1;i <= n;i++) {
        int w1,w2,v;
        cin >> w1 >> w2 >> v;
        for (int j1 = m1;j1 >= w1;j1--) {
            for (int j2 = m2;j2 >= w2;j2--) f[j1][j2] = max (f[j1][j2],f[j1 - w1][j2 - w2] + v);
        }
    }
    cout << f[m1][m2] << endl;
    return 0;
}