AcWing 9.分组背包问题

题目链接：http://www.acwing.com/problem/content/9/

博客链接：https://www.cnblogs.com/marswithme/p/16778389.html

放AC代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n, m;
 4 int v[110][110], w[110][110], s[110];
 5 int dp[110];
 6 
 7 int main()
 8 {
 9     cin >> n >> m;
10     for(int i = 1; i <= n; i ++)
11     {
12         cin >> s[i];
13         for(int j = 0; j < s[i]; j ++)
14             cin >> v[i][j] >> w[i][j];
15     }
16 
17     // 由于每组物品只能选一个，所以可以覆盖之前组内物品的最优解来取最大值
18     for(int i = 1; i <= n; i ++)
19         for(int j = m; j >= 0; j --)
20             for(int k = 0; k <= s[i]; k ++)
21                 if(v[i][k] <= j)
22                     dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k]);
23 
24     cout << dp[m] << endl;
25 
26     return 0;
27 }