分组背包问题

本文主要是介绍分组背包问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Acwing 分组背包问题
有 N 组物品和一个容量是 V 的背包。每组物品有若干个，同一组内的物品最多只能选一个。每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。输出最大价值。
解法:相较于其它背包,这个题目的分组背包就是对于一组物品我们只能进行选择一个,那么我们还是需要进行考虑当前有状态转移有几个维度,当然第一维度肯定是for(int i = 1; i <= n; i++)表示第几组物品,第二维度就是for(int j = m; j >= 0; j–)表示体积维度,第三维度我们需要进行考虑如何进行选择一组内的一个物品那么就是for(int k = 1; k <= a[i].s; k++)表示当前第i组的第几个物品,那么之后我们就要考虑dp的状态转移
由于此时的第二维度j表示体积的不一定大于当前选择物品体积,我们就if(j >= a[i].v[k])dp[j] = max(dp[j], dp[j - a[i].v[k]] + a[i].w[k]);这样就好了!

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e2 + 5; 
struct node{
	int s;
	int v[maxn];
	int w[maxn];
}a[maxn];
int dp[maxn];
int main(){
	int n,m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> a[i].s;
		for(int j = 1; j <= a[i].s; j++){
			cin >> a[i].v[j] >> a[i].w[j];
		}
	}
	for(int i = 1; i <= n; i++){//第几组物品 
		for(int j = m; j >= 0; j--){//体积 
			for(int k = 1; k <= a[i].s; k++){//第几个 
				if(j >= a[i].v[k])
				dp[j] = max(dp[j], dp[j - a[i].v[k]] + a[i].w[k]);
			}
		}
	}
	cout << dp[m] << '\n';
}

这篇关于分组背包问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！