分组背包问题

主件与附近有4种组合：

1. 只有主件
2. 主件+附件1
3. 主件+附件2
4. 主件+附件1+附件2

这4种组合构成一组，只能从这一组中选择一种组合！因此就将该问题转换为分组背包问题。

代码

#include<iostream>
#include<math.h>
#include<bits/stdc++.h>

using namespace std;

int f[32000];

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> v(m+1);
    vector<int> w(m+1);
    vector<int> q(m+1);

    unordered_map<int, vector<int>> mp;
    for(int i = 1; i <= m; i ++){
        cin >> v[i] >> w[i] >> q[i];
        w[i] = v[i]*w[i];
        if(q[i]){
            mp[q[i]].push_back(i);
        }
    }   
    vector<vector<int>> V;
    vector<vector<int>> W;
    for(int i = 1; i <= m; i ++){
        vector<int> v_tmp;
        vector<int> w_tmp;
        if(mp.count(i)){
            v_tmp.push_back(v[i]);
            w_tmp.push_back(w[i]);
            if(mp[i].size() == 1){
                v_tmp.push_back(v[i] + v[mp[i][0]]);
                w_tmp.push_back(w[i] + w[mp[i][0]]);
            }
            if(mp[i].size() == 2){
                v_tmp.push_back(v[i] + v[mp[i][0]]);
                w_tmp.push_back(w[i] + w[mp[i][0]]);

                v_tmp.push_back(v[i] + v[mp[i][1]]);
                w_tmp.push_back(w[i] + w[mp[i][1]]);

                v_tmp.push_back(v[i] + v[mp[i][0]] + v[mp[i][1]]);
                w_tmp.push_back(w[i] + w[mp[i][0]] + w[mp[i][1]]);
            }
        }else if(q[i] == 0){
            v_tmp.push_back(v[i]);
            w_tmp.push_back(w[i]);
        }
        V.push_back(v_tmp);
        W.push_back(w_tmp);
    }
    for(int i = 1; i <= m; i++){
        for(int j = n; j >=0; j --){
            for(int k = 0; k < V[i-1].size(); k++){
                if(j >= V[i-1][k]){
                    f[j] = max(f[j], f[j-V[i-1][k]] + W[i-1][k]);
                }
            }
        }
    }

    cout << f[n];

    return 0;

}

分组背包问题描述

有 N 组物品和一个容量是 V 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 v[i][j]，价值是 w[i][j]，其中 i 是组号，j 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。