AcWing 487. 金明的预算方案
- 体积:n元钱
- 价值:物品重要度*体积
- 若干个物品组 每个物品至多有两个附件 即每组最多4个分支
- 只购买主件,
- 主件+附件1
- 主件+附件2
- 主件+附件1+附件2
- 初始化时 主件则建立新组i存入[i] [0],附件1则计算主件+附件1价格和价值[i] [1],同理附件2 [i] [ 2],同时建立[i] [3] 主件+附件1+附件2
$$ DP \begin{cases} 状态表示f(i,j) \begin{cases} 集合:所有只考虑前i组物品,物品价格不超过n元的所有物品与重要度的乘积 \\ 属性:max \end{cases} \\ note:物品价格都是10的整倍数,即j\le N/10即可,且v和n/=10 \\ 状态计算——集合划分 \begin{cases} 第i组物品不购买\qquad f[i-1][j] \\ 第i组物品购买主件\qquad f(i-1,j-v[i][0])+w[i][0] \\ 第i组物品购买主件+附件1\qquad f(i-1,j-v[i][1])+w[i][1] \\ 第i组物品购买主件+附件2\qquad f(i-1,j-v[i][2])+w[i][2] \\ 第i组物品购买主件+附件2+附件1\qquad f(i-1,j-v[i][3])+w[i][3] \end{cases} \\ f(i,j)=\max\limits_{k=1}^3(f(i-1,j),f(i-1,j-v[i][k])+w[i][k]) \end{cases} \\ 本题通过输入并计算转换为acw1013.机器分配\\ 时间复杂度N/10*M*4 $$
#include <iostream>
using namespace std;
const int N = 32000 / 10 + 10, M = 66;
int f[N];
int m, n;
int v[M][4], p[M][4];
void input() {
int V, P, Q;
//将附件和主件录入同一组内,将p优化成p*v
for (int i = 1; i <= m; i++) {
cin >> V >> P >> Q;
V /= 10;
if (!Q) {
v[i][0] = V;
p[i][0] = P * V;
} else {
int j = 1;
while (v[Q][j])j++;
v[Q][j] = V;
p[Q][j] = P * V;
}
}
//购买附件时仍需购买主件,故将主附件合并处理
for (int i = 1; i <= m; i++) {
if (!v[i][0])continue;
if (v[i][1]) {
v[i][1] += v[i][0];
p[i][1] += p[i][0];
}
if (v[i][2]) {
v[i][3] = v[i][1] + v[i][2];
v[i][2] += v[i][0];
p[i][3] = p[i][1] + p[i][2];
p[i][2] += p[i][0];
}
}
}
int DP() {
for (int i = 1; i <= m; i++)
for (int j = n; j; j--)
for (int k = 0; k < 4; k++)
if (!v[i][k])break;
else if (j >= v[i][k]) f[j] = max(f[j], f[j - v[i][k]] + p[i][k]);
return f[n];
}
int main() {
cin >> n >> m;
n /= 10;
input();
cout << DP() * 10 << endl;
return 0;
}