AcWing 487. 金明的预算方案
原题链接
中等
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
const int N = 60, M = 32010;
int m, n;
PII master[N];
vector<PII> servant[N];
vector<int> V[N], W[N]; // 分组背包中使用的 V[][] 和 W[][]
int cnt; // 记录分组背包的组数
int f[N][M];
int main() {
scanf("%d%d", &m, &n);
int v, p, q;
for (int i = 1; i <= n; i++) {
scanf("%d%d%d", &v, &p, &q);
if (q == 0) master[i] = {v, v * p};
else servant[q].push_back({v, v * p});
}
// 转化为分组背包问题
for (int i = 1; i <= n; i++) {
if (master[i].x) {
cnt++;
int size = servant[i].size();
for (int j = 0; j < 1 << size; j++) {
// 记录第 cnt 组背包中第 j 个物品的体积和价值
int v = master[i].x, w = master[i].y; // 由于必须选主件 所以必须带上主件的体积和价值
for (int k = 0; k < size; k++)
if (j >> k & 1)
v += servant[i][k].x, w += servant[i][k].y;
V[cnt].push_back(v), W[cnt].push_back(w);
}
}
}
// 进行分组背包 DP
for (int i = 1; i <= cnt; i++)
for (int j = 0; j <= m; j++) {
f[i][j] = f[i - 1][j];
for (int k = 0; k < V[i].size(); k++)
if (j >= V[i][k]) f[i][j] = max(f[i][j], f[i - 1][j - V[i][k]] + W[i][k]);
}
printf("%d", f[cnt][m]);
return 0;
}