题解 华为机试题 购物单 分组背包问题

#include <bits/stdc++.h>

using namespace std;

const int N = 70, M = 32010;
// <value, value * priority>
typedef pair<int, int> PII;
#define x first
#define y second
int n, m;
int f[M];
PII masters[N];
vector<PII> accessory[N];

int main(){
    cin >> m >> n;
    for(int i = 1; i <= n; i ++){
        int v, p, q;
        cin >> v >> p >> q;
        if(q == 0)    masters[i] = {v, v * p};
        else{
            accessory[q].push_back({v, v * p});
        }
    }
    
  // 二进制优化代码
    for(int i = 1; i <= n; i ++){
        for(int u = m; u >= 0; u --){
            for(int j = 0; j < 1 << accessory[i].size(); j ++){
                int volume = masters[i].x;
                int value = masters[i].y;
                for(int k = 0; k < accessory[i].size(); k ++){
                    if(j >> k & 1){
                        volume += accessory[i][k].x;
                        value += accessory[i][k].y;
                    }
                }
                if( u >= volume)    f[u] = max(f[u], f[u - volume] + value);
            }
        }
    }
    cout << f[m] << endl;
    return 0;
    
}