P1757 通天之分组背包

admin

https://www.luogu.org/problemnew/show/P1757

题目背景
直达通天路·小A历险记第二篇

题目描述
自01背包问世之后，小A对此深感兴趣。一天，小A去远游，却发现他的背包不同于01背包，他的物品大致可分为k组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。

输入输出格式
输入格式：
两个数m,n，表示一共有n件物品，总重量为m

接下来n行，每行3个数ai,bi,ci，表示物品的重量，利用价值，所属组数

输出格式：
一个数，最大的利用价值

输入输出样例
输入样例#1：
45 3
10 10 1
10 5 1
50 400 2
输出样例#1：
10
说明
1<=m<=1000 1<=n<=1000 组数t<=100

吴语林

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <cmath>
   
4. #include <cstring>
   
5. #include <map>
   
6. #include <string>
   
7. #include <vector>
   
8. #include <queue>
   
9. #include <stack>
   
10. #include <cstdio>
    
11. #include <cstdlib>
    
12. using namespace std;
    
13. vector <int> v[1100],w[1100];
    
14. int f[1100],m,n,T=0;
    
15. int main()
    
16. {
    
17.     scanf("%d%d",&m,&n);
    
18.     for(int i=1;i<=n;i++)
    
19.     {
    
20.         int v1,w1,a1;
    
21.         scanf("%d%d%d",&w1,&v1,&a1);
    
22.         v[a1].push_back(v1);
    
23.         w[a1].push_back(w1);
    
24.         T=max(T,a1);
    
25.     }
    
26.     for(int i=1;i<=T;i++)
    
27.             for(int j=m;j>=0;j--)
    
28.                     for(int k=0;k<v[i].size();k++)
    
29.                             if(j>=w[i][k])
    
30.                                     f[j]=max(f[j],f[j-w[i][k]]+v[i][k]);
    
31.     printf("%d",f[m]);
    
32.     return 0;
    
33. }

复制代码

胡雨菲菲

1. #include <cstdio>
   
2. #include <algorithm>
   
3. typedef long long LL;
   
4. using namespace std;
   
5. 
   
6. const int N = 1010;
   
7. const LL INF = 1ll << 62;
   
8. 
   
9. struct A {
   
10.     LL cost, val, group;
    
11.     bool operator < (const A &x) {
    
12.         return group < x.group;
    
13.     }
    
14. }a[N];
    
15. 
    
16. struct Group {
    
17.     LL s, t, small;
    
18. }g[N];
    
19. 
    
20. LL f[N];
    
21. 
    
22. int main() {
    
23.     LL V, n;
    
24.     scanf("%lld%lld", &V, &n);
    
25.     for(int i = 1; i <= n; i++) {
    
26.         scanf("%lld%lld%lld", &a[i].cost, &a[i].val, &a[i].group);
    
27.     }
    
28.     sort(a + 1, a + n + 1);
    
29.     for(int i = 1; i <= n; i++) {
    
30.         if(a[i].group != a[i - 1].group) {
    
31.             g[a[i].group].s = i;
    
32.         }
    
33.         g[a[i].group].t = i;
    
34.     }
    
35.     for(int i = 1; i <= a[n].group; i++) {
    
36.         g[i].small = INF;
    
37.         for(int j = g[i].s; j <= g[i].t; j++) {
    
38.             g[i].small = min(g[i].small, a[j].cost);
    
39.         }
    
40.     }
    
41.    
    
42.     for(int k = 1; k <= a[n].group; k++) { /// k-th group
    
43.         for(int i = V; i >= g[k].small; i--) { /// i V
    
44.             for(int j = g[k].s; j <= g[k].t; j++) { /// j which
    
45.                 if(i >= a[j].cost) {
    
46.                     f[i] = max(f[i], f[i - a[j].cost] + a[j].val);
    
47.                 }
    
48.             }
    
49.         }
    
50.     }
    
51.     LL ans = 0;
    
52.     for(int i = 1; i <= V; i++) {
    
53.         ans = max(ans, f[i]);
    
54.     }
    
55.     printf("%lld", ans);
    
56.     return 0;
    
57. }
    

复制代码