动态规划学习（分组背包）

分组背包的定义

分组背包是相比于01背包来讲，其就是多了一个组，给你n个组，每个组里有各自的物品，每个组里的物品只能选择一个，问你，选出来的最大价值是多少

这里我们的遍历顺序的三层循环，最外层的循环遍历组数，中间的循环遍历背包容量，最后的循环遍历的是每个组内的物品数

模版

for(int i=1;i<=n;i++)//总共有n组物品
{
	for(int j=m;j>=0;j--)//背包容量最大为m
	{
		for(int k=1;k<=cnt;k++)//每组物品有cnt个
		{
			if(j>=w[i][k])//如果背包的容量还能装下第i组的第k个物品
			{
				dp[j]=max(dp[j],dp[j-w[i][k]]+v[i][k]);
			}
		}
	}
}

例题

P1757 通天之分组背包

很标准的分组背包模版题，我们只需要统计组数，以及每个组内的物品个数，然后进行分组背包的板子就OK了

#include<bits/stdc++.h>
using namespace std;

int n,m;
int w[105][1005];
int v[105][1005];
int cnt[105];
int dp[1005];
signed main()
{
	cin>>m>>n;
	int a,b,c;
	int num=0;//统计组数 
	for(int i=1;i<=n;i++)
	{
		cin>>a>>b>>c;
		cnt[c]++;
		w[c][cnt[c]]=a;
		v[c][cnt[c]]=b;
		num=max(num,c);
	}
	
	for(int i=1;i<=num;i++)
	{
			for(int j=m;j>=0;j--)
			{
				for(int k=1;k<=cnt[i];k++)
				{
					if(j>=w[i][k])
					dp[j]=max(dp[j],dp[j-w[i][k]]+v[i][k]);
				}
			}
	}
	cout<<dp[m];
	return 0;
 } 

 P5322 [BJOI2019] 排兵布阵

题意：就是说和对手总共有s个，游戏里有n个城堡，以及每个人的士兵有m个，每个对手都会向城堡中派一些人，当你派去的士兵严格比对手的士兵的两倍还多才能占领这个城堡，如果是第i个城堡，那么就得到i分

思路：乍一看，会觉得，这题和分组背包有什么关系，我们分组背包选的只有一个，但是你可以向每个城堡派人，这也能是分组背包 如果我们正常来看，就是从每个玩家的入手，肯定就和分组背包无缘了，我们可以从城堡的角度来看，我们派去每个城堡的士兵数每回合都是固定的，如果我们将每个对手派往对应 i 城堡的人数进行排序，然后选择到底要派多少人，如果派的人比第k个还多，那么k之前的都可以选，所以这题要从城堡的角度考虑问题

#include<bits/stdc++.h>
using namespace std;

int s,n,m;
int a[105][105];
int dp[20005];

int main()
{
	cin>>s>>n>>m;
	for(int i=1;i<=s;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>a[j][i];
		}
	}
	for(int i=1;i<=n;i++)
	{
		sort(a[i]+1,a[i]+s+1);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=m;j>=0;j--)
		{
			for(int k=1;k<=s;k++)
			{
				if(j>2*a[i][k])
				{
					dp[j]=max(dp[j],dp[j-2*a[i][k]-1]+i*k);
				}
			}
		}
	}
	cout<<dp[m];
	return 0;
}