一个典型的有依赖的背包问题。这里每种物品最多只可能有三个附属品，我看错了题目条件，写了一个可能有n个附属品的版本。o(╯□╰)o
可以将物品按照附属关系先进行分组，对每组都来一次01背包。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
#include <cstdio>#include <cstring>#include <algorithm>using
namespace
std;
const
int
maxn = 100;
const
int
maxv = 3201;
struct
Item {
int
cost,w,child,cnum[maxn],fa;
};Item itm[maxn];int
f[maxv],g[maxv];
int
main() {
int
n,limv;
scanf("%d%d",&limv,&n);
for(int
i = 1;i <= n;i++) {
scanf("%d%d%d",&itm[i].cost,&itm[i].w,&itm[i].fa);
if(itm[i].fa) itm[itm[i].fa].cnum[itm[itm[i].fa].child++] = i;
itm[i].cost /= 10;
}
limv /= 10;
for(int
i = 1;i <= n;i++) if(!itm[i].fa) {
memset(g,0,sizeof(g));
for(int
j = 0;j < itm[i].child;j++) {
Item &now = itm[itm[i].cnum[j]];
for(int
v = limv;v >= now.cost;v--) {
g[v] = max(g[v],g[v - now.cost] + now.cost * now.w);
}
}
for(int
v = limv;v >= itm[i].cost;v--) {
for(int
v1 = v - itm[i].cost; v1 >= 0;v1--) {
f[v] = max(f[v],f[v - itm[i].cost - v1] + g[v1] + itm[i].cost * itm[i].w);
}
}
}
printf("%d\n",f[limv] * 10);
return
0;
} |