题意
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。
更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。
今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：
如果要买归类为附件的物品，必须先买该附件所属的主件。
每个主件可以有0个、1个或2个附件。
附件不再有从属于自己的附件。
金明想买的东西很多，肯定会超过妈妈限定的N元。
于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。
他还从因特网上查到了每件物品的价格（都是10元的整数倍）。
他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j 1 ， j 2 ， … ， j k ，则所求的总和为：
v [ j 1 ] ∗ w [ j 1 ] + v [ j 2 ] ∗ w [ j 2 ] + … + v [ j k ] ∗ w [ j k ] （其中*为乘号）
请你帮助金明设计一个满足要求的购物单。
思路
分组背包
先把所有主件存起来 然后把每个主件对应的副件存在一个 vector 中
对每个物品遍历 如果它是主件的话 就枚举一下取哪些它的副件 这里可以用二进制枚举
最后求出最大值即可
代码
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 998244353 #define endl '\n' #define int long long using namespace std; inline int gcd(int a, int b) { return b ? gcd(b, a%b) : a; } inline int lowbit(int x) { return x & -x; } typedef long long LL; typedef pair<int, int>PII; const int N = 70; int n, m; PII master[N]; //主件 vector<PII>servent[N]; //主件下面的附件 int f[32050]; void solve() { cin >> m >> n; for (int i = 1; i <= n; ++i) { int v, w, q; cin >> v >> w >> q; if (q == 0) { master[i] = { v,v * w }; } else servent[q].push_back({ v,v*w }); } for (int i = 1; i <= n; ++i) { if (master[i].first) { //如果是一个主件 for (int j = m; j >= 0; --j) { for (int k = 0; k < 1 << servent[i].size(); ++k) { int v = master[i].first; int w = master[i].second; for (int t = 0; t < servent[i].size(); ++t) { if ((k >> t) & 1) { v += servent[i][t].first; w += servent[i][t].second; } } if (j >= v)f[j] = max(f[j], f[j - v] + w); } } } } cout << f[m] << endl; } signed main() { //int t; cin >> t; //while(t--) solve(); return 0; }
