有 $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
其实跟01背包一样的
直接设方程f[i][j][k]表示从前i个物品中选体积不超过j重量不超过k的最大价值的方案集合
不选当前物品 f[i][j][k] = f[i - 1][j][k]
选择当前物品 f[i][j][k] = f[i - 1][j - v][k - m]
最后取max就好了
#include "bits/stdc++.h"
#define int long long
using namespace std;
const int N = 1010;
int f[N][N];
int n, V, M;
int w[N], m[N], v[N];
signed main(void) {
cin >> n >> V >> M;
for (int i = 1; i <= n; i++) {
cin >> v[i] >> m[i] >> w[i];
}
for (int i = 1; i <= n; i++) {
for (int j = V; j >= v[i]; j--) {
for (int k = M; k >= m[i]; k--) {
f[j][k] = max(f[j][k], f[j - v[i]][k - m[i]] + w[i]);
}
}
}
cout << f[V][M] << '\n';
return 0;
}