分组背包

将背包分为n堆，每堆最多拿一个或者不拿。求最大的价值。

对于每一堆只能选一个或者不选，可以转化为01背包的问题。

1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1006;
 4 int n,c;///n为物品个数，c为背包重量
 5 struct Point{
 6     int k; ///k为该堆物品的数量
 7     int v[106],p[106]; ///v为该堆物品里面第k个物品的重量，p为价值
 8 }b[maxn];
 9 int dp[maxn];
10 
11 int main()
12 {
13     ios::sync_with_stdio(0); std::cin.tie(0);
14     int T;
15     while( cin >> T){
16         while(T--){
17             memset( dp, 0, sizeof dp);
18             cin >> n >> c;
19             for(int i=1;i<=n;i++){
20                 cin >> b[i].k;
21                 for(int j=1;j<=b[i].k;j++)
22                     cin >> b[i].v[j] >> b[i].p[j];
23             }
24 
25             int mid;
26             for(int i=1;i<=n;i++){
27                 for(int j=c;j>0;j--){ ///01背包，多一重循环枚举该堆的最优值
28                     for(int k=1;k<=b[i].k;k++){
29                         if(j>=b[i].v[k])
30                         dp[j]=max(dp[j-b[i].v[k]]+b[i].p[k],dp[j]);
31                     }
32                 }
33             }
34             cout << dp[c] <<endl;
35         }
36     }
37     return 0;
38 }

原文链接: https://www.cnblogs.com/ZQUACM-875180305/p/9042414.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍