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

walk_alone

1. #include <cstdio>
   
2. #include <algorithm>
   
3. using namespace std;
   
4. int thing[101][1001],a[1001],b[1001],cnt[101],f[1001];
   
5. int main()
   
6. {
   
7.         int n,m,c,maximum=-999;
   
8.         scanf("%d%d",&m,&n);
   
9.         for(int i=1;i<=n;i++)
   
10.         {
    
11.                 scanf("%d%d%d",&a[i],&b[i],&c);
    
12.                 thing[c][++cnt[c]]=i;
    
13.                 maximum=max(maximum,c);
    
14.         }
    
15.         for(int k=1;k<=maximum;k++)
    
16.                 for(int v=m;v>=0;v--)
    
17.                         for(int i=1;i<=cnt[k];i++)
    
18.                                 if(v>=a[thing[k][i]])
    
19.                                         f[v]=max(f[v],f[v-a[thing[k][i]]]+b[thing[k][i]]);
    
20.         printf("%d",f[m]);
    
21.         return 0;
    
22. }

复制代码

张笑宇

1. #include<iostream>
   
2. using namespace std;
   
3. int n,sumv;
   
4. const int mx=1010;
   
5. int v[mx],w[mx],t[mx];
   
6. int dp[mx],i,j,k;
   
7. int sumc,c[110][110],countc[110];///sumc总组数
   
8. int main()///countc[i]第i组个数
   
9. {
   
10.     cin>>sumv>>n;
    
11.     for (i=1; i<=n; i++)
    
12.     {
    
13.         cin>>v[i]>>w[i]>>t[i];
    
14.         sumc=max(sumc,t[i]);
    
15.         countc[t[i]]++;
    
16.         c[t[i]][countc[t[i]]]=i;
    
17.     }
    
18.     for (i=1; i<=sumc; i++)///枚举组数
    
19.         for (j=sumv; j>=0; j--)
    
20.             for (k=1; k<=countc[i]; k++)
    
21.                 if (j>=v[c[i][k]])
    
22.                     dp[j]=max(dp[j],dp[j-v[c[i][k]]]+w[c[i][k]]);
    
23.     cout<<dp[sumv];
    
24.     return 0;
    
25. }
    

复制代码

张笑宇

分组背包+跳转表