【分组背包】洛谷刷题合集

模版题P1757

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,c,cnt;
int dp[1005];
map<int,int> vis;
vector<int> v[1005],w[1005];
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>a>>b>>c;
		if(vis[c]==0){
			++cnt;
			vis[c]=cnt;
		}
		w[vis[c]].push_back(a);
		v[vis[c]].push_back(b);
	}
	for(int i=1;i<=cnt;i++){
		for(int j=m;j>=0;j--){
			for(int k=0;k<w[i].size();k++){
				if(w[i][k]<=j) dp[j]=max(dp[j],dp[j-w[i][k]]+v[i][k]);
			}
		}
	}
	cout<<dp[m];
	return 0;
}

洛谷P1064

• 实现方法1：

1. 识别出这是“主件带附件”的依赖背包。
2. 因为每个主件最多 2 个附件，所以每个主件组最多只有 4 种买法：
   只买主件
   主件 + 附件1
   主件 + 附件2
   主件 + 附件1 + 附件2
3. 把这 4 种买法当成分组背包里的一组物品。
4. 套用分组背包模板：外层主件，内层容量逆序，组内枚举方案。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> w(m + 1), v(m + 1);
    vector<vector<int>> attach(m + 1); // 主件 -> 附件编号
    vector<bool> isAttach(m + 1, false);
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        w[i] = a;
        v[i] = a * b;
        if (c) {
            isAttach[i] = true;
            attach[c].push_back(i);
        }
    }
    vector<int> dp(n + 1, 0);
    for (int i = 1; i <= m; i++) {
        if (isAttach[i]) continue; // 只处理主件
        // 收集当前主件的所有可能组合：{花费, 价值}
        vector<pair<int, int>> items;
        items.push_back({w[i], v[i]}); // 只买主件
        // 附件最多两个，直接枚举
        if (attach[i].size() >= 1) {
            int a1 = attach[i][0];
            items.push_back({w[i] + w[a1], v[i] + v[a1]});
        }
        if (attach[i].size() >= 2) {
            int a1 = attach[i][0], a2 = attach[i][1];
            items.push_back({w[i] + w[a2], v[i] + v[a2]});
            items.push_back({w[i] + w[a1] + w[a2], v[i] + v[a1] + v[a2]});
        }

        // 分组背包：逆序枚举容量，组内物品只能选一个
        for (int j = n; j >= 0; j--) {
            for (auto [cost, val] : items) {
                if (j >= cost) {
                    dp[j] = max(dp[j], dp[j - cost] + val);
                }
            }
        }
    }
    cout << dp[n] << endl;
    return 0;
}

• 实现方法2：不显式列出 4 种组合，而是引入 ep[j] 表示“必须选当前主件”时的最优值。

1. 先强制选主件，得到 ep[j] = dp[j-w[i]] + v[i]。
2. 再对附件做 0/1 背包，把附件逐个叠加到 ep 上：
   $ep[j]=max(ep[j],ep[j-w[p]]+v[p])$
3. 最后用 dp[j] = max(dp[j], ep[j]) 把“选当前组某个方案”合并回全局。

#include<bits/stdc++.h>
using namespace std;
const int maxn=32005;
int w[maxn],v[maxn],m,n,dp[maxn],ep[maxn];
vector<int> g[maxn];
bool fs[maxn];
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		w[i]=a;
		v[i]=a*b;
		if(c){
			fs[i]=1;
			g[c].push_back(i);
		} 
	}
	for(int i=1;i<=m;i++){
		if(!fs[i]){
			for(int j=n;j>=w[i];j--){
				dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
				ep[j]=dp[j-w[i]]+v[i];
			}
			for(int k=0;k<g[i].size();k++){
				int p=g[i][k];
				for(int j=n;j>=w[p]+w[i];j--){
					ep[j]=max(ep[j],ep[j-w[p]]+v[p]);
					dp[j]=max(dp[j],ep[j]);
				}
			}
		}
	}
	cout<<dp[n];
	return 0;
}

洛谷P2967

#include<bits/stdc++.h>
using namespace std;
int n,v,p[100][20],gp[100][20],gn[100],dp[100005],ep[100005],pp[100];
int main(){
	cin>>n>>v;
	for(int i=1;i<=n;i++){
		cin>>pp[i]>>gn[i];
		for(int j=1;j<=gn[i];j++)
			cin>>p[i][j]>>gp[i][j];
	}
	for(int i=1;i<=n;i++){
		for(int j=v;j>=pp[i];j--)
			ep[j]=dp[j-pp[i]];
		for(int k=1;k<=gn[i];k++){
			for(int j=v;j>=p[i][k]+pp[i];j--){
				ep[j]=max(ep[j],ep[j-p[i][k]]+gp[i][k]);
				dp[j]=max(dp[j],ep[j]);
			}
		}
	}
	cout<<dp[v];
	return 0;
} 

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/ChaoyingL/article/details/167038925