牛客 华为笔试题 购物单

牛客 华为笔试题 购物单

思路：

购买副产品的前提只能先购买主键，所以相当于分组背包，每个分组中只能购买主键的同时购买或者不够买副键。

代码：

#include<iostream>
#include<vector>
using namespace std;

typedef pair<int,int>PII;
const int N=70,M=32010;
int n,m;
int f[N][M];

vector<PII>ve[N];
PII g[N];


int main(){
    cin >> m >> n;
    for (int i = 1; i <= n; i++) {
        int v, w, q;
        cin >> v >> w >> q;
        if (!q) g[i] = {v, v * w};
        else ve[q].push_back({v, v * w});
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            //不选
            f[i][j] = f[i - 1][j];
	    //k = 0 相当于不够买副键
            for (int k = 0; k < 1 << ve[i].size(); k++) {

                int v = g[i].first, w = g[i].second;

                for (int u = 0; u < ve[i].size(); u++) {
                    if (k >> u & 1) {
                        v += ve[i][u].first;
                        w += ve[i][u].second;
                    }
                }
                if (j >= v) f[i][j] = max(f[i][j], f[i - 1][j - v] + w);
            }

        }
    }
    
    cout<<f[n][m];
    return 0;
}