P1064 金明的预算方案（01背包||有依赖的背包）

直接01背包硬刚，虽然容易理解，但是完全不适合附件多的情况

 1 /*
 2 1、只选主件
 3 2、选主件和附件1
 4 3、选主件和附件2
 5 4、选主件和附件1.2
 6 */
 7 #include <iostream>
 8 #include<string>
 9 #include<cstdio>
10 #include<cmath>
11 #define ll long long
12 using namespace std;
13 int V[70][3],P[70][3];
14 int f[40000];
15 int cost1(int x)
16 {
17     return V[x][0];
18 }
19 int cost2(int x)
20 {
21     return V[x][0]+V[x][1];
22 }
23 int cost3(int x)
24 {
25     return V[x][0]+V[x][2];
26 }
27 int cost4(int x)
28 {
29     return V[x][0]+V[x][1]+V[x][2];
30 }
31 int main(void)
32 {
33     int n,m;
34     cin>>n>>m;
35     for(int i=1;i<=m;i++)
36     {
37         int v,p,q;
38         cin>>v>>p>>q;
39         if(!q)
40         {
41             V[i][0]=v;
42             P[i][0]=p;
43         }
44         else//附件
45         {
46             if(V[q][1]==0)//附件1
47             {
48                 V[q][1]=v;
49                 P[q][1]=p;
50             }
51             else//附件2
52             {
53                 V[q][2]=v;
54                 P[q][2]=p;
55             }
56         }
57     }
58     for(int i=1;i<=m;i++)//遍历物品
59     {
60         for(int j=n;j>=0;j--)//遍历容量（钱数），3e4*60=1e5，完全能过
61         {
62             if(j>=cost1(i))
63             {
64                 f[j]=max(f[j-cost1(i)]+V[i][0]*P[i][0],f[j]);
65             }
66             if(j>=cost2(i))
67             {
68                 f[j]=max(f[j],f[j-cost2(i)]+V[i][0]*P[i][0]+V[i][1]*P[i][1]);
69             }
70             if(j>=cost3(i))
71             {
72                 f[j]=max(f[j],f[j-cost3(i)]+V[i][0]*P[i][0]+V[i][2]*P[i][2]);
73             }
74             if(j>=cost4(i))
75             {
76                 f[j]=max(f[j],f[j-cost4(i)]+V[i][0]*P[i][0]+V[i][1]*P[i][1]+V[i][2]*P[i][2]);
77             }
78         }
79     }
80     cout<<f[n];
81     return 0;
82 }

非树形的依赖背包还是比较简单的，就是用01背包做预处理，然后再是分组背包

01背包将这个主件和附件的所有情况都考虑清楚了，分组背包则是最后的答案

 1 #include<cstring>
 2 #include<iostream>
 3 using namespace std;
 4 struct node
 5 {
 6     int v,p,q;
 7 }a[1010];
 8 int f[5000010],h[5000010];
 9 int main(void)
10 {
11     int n,m;
12     cin>>n>>m;
13     for(int i=1;i<=m;i++)
14     {
15         cin>>a[i].v>>a[i].p>>a[i].q;
16         a[i].p*=a[i].v;//题目所要求的价格乘以重要度
17     }
18     for(int i=1;i<=m;i++)
19     {
20         if(!a[i].q)
21         {
22             for(int j=1;j<a[i].v;j++)//初始化
23             {
24                 h[j]=0;
25             }
26             for(int j=a[i].v;j<=n;j++)//考虑只买主件的情况
27             {
28                 h[j]=f[j-a[i].v]+a[i].p;
29             }
30             for(int j=1;j<=m;j++)//接下来对每个附件进行一次01背包，这样一来就不用考虑是买几个附件了
31             {
32                 if(a[j].q==i)
33                 {
34                     for(int k=n;k>=a[i].v+a[j].v;k--)
35                     {
36                         h[k]=max(h[k],h[k-a[j].v]+a[j].p);
37                     }
38                 }
39             }
40             for(int j=a[i].v;j<=n;j++)
41             {
42                 f[j]=max(f[j],h[j]);
43             }   
44         }
45     }
46     cout<<f[n]<<endl;
47     return 0;
48 }

来自洛谷题解，做下笔记