【c++入门（2）】分组背包 and 多重背包

一、 分组背包
描述：

问题描述：有n种物品，每种物品有一个，其中第i种物品的重量为w[i]，价值为v[i]，这n
个物品被分成了k组，每组中的物品相互冲突，最多只能选一个，选一些物品装到一个承重
量为C的背包里，使得背包内物品总重量不超过C的前提下价值尽量大。

这道题就是说n个物品被分成了k组，每一组可以拿一个或者不拿，有一个背包容量为C的背包问获得的的最大价值是多少？
分组背包是在0-1背包的基础上将每个物品划分到一个分组中，首先考虑分组。
对于每个分组有两种可选的决策：
① 不从该分组中选择物品。
② 从该分组中选择物品。
将分组看成一个大物品，那么可以用类似于0-1背包的方式进行状态定义。
定义状态：d(i, j)表示为前i个分组分配j的背包空间，可以获得的最大价值。
状态转移方程：
① 不从分组i中取物品：d(i, j) = d(i-1, j);
② 从分组i中取1个物品，由于分组i中有多个物品，该如何决策呢？
遇到问题啦！

决策2：从分组i中取1个物品可以分解为多个小决策：
假设分组i中有cnt[i]个物品，且所有物品中只能选一个，此时有cnt[i]种选择，显然那
种选择可以使得获得的价值最大就使用那种选择。
② 从分组i中取1个物品：d(i, j) = max(d(i-1, j- w[k]) + v[k]); (k为分组i中的物品)。

	for(int i=1;i<=m;i++){  //分组 
		for(int j=1;j<=c;j++){  //背包 
			dp[i][j]=dp[i-1][j];
			for(k∈i){
				if(j>=w[k]){
					dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[k]);
				}
			}
		}
	}

k∈i分组解决方案：
方法1：淳朴暴力，看看是否属于该集合
方法2：标记，桶存储这个集合有多少个物品，并且用一个二维的 cnt[分组编号][这个分组的第几个] 来存储这个物品在n个物品中是第几个。
第一种方法实现：

for(int k=1;k<=n;k++){
	if(所属分组[k]==i){
		if(可以放)状态转移方程
	}
}

第二种方法实现：

for(int i=1;i<=n;i++){
	cin>>w[i]>>v[i]>>x;
	t=max(t,x);
	b[x]++;
	g[x][b[x]]=i;
}
for(int i=1;i<=t;i++){
	for(int j=m;j>=0;j--){
		for(int k=1;k<=b[i];k++){
			if(j>=w[g[i][k]]) dp[j]=max(dp[j],dp[j-w[g[i][k]]]+v[g[i][k]]);  //这里可以滚动~，后面还可以优化循环 时间复杂度
		}
	}
}
cout<<dp[m];

来一刀 道模板：

通天之分组背包
题目描述

自01背包问世之后，小A对此深感兴趣。一天，小A去远游，却发现他的背包不同于01背包，他的物品大致可分为k组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。
输入格式

两个数m,n，表示一共有n件物品，背包大小为m

接下来n行，每行3个数ai,bi,ci，表示物品的重量，利用价值，所属组数
输出格式

一个数，最大的利用价值
输入输出样列
输入样例1：

45 3
10 10 1
10 5 1
50 400 2

输出样例1：

10

说明

1<=m<=1000 1<=n<=1000 组数t<=100

水模板：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int n,m,t,x;
int w[1100],v[1100],b[1100],g[1100][1100],f[1100];
int main()
{
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>v[i]>>x;
		t=max(t,x);
		b[x]++;
		g[x][b[x]]=i;
	}
	for(int i=1;i<=t;i++){
		for(int j=m;j>=0;j--){
			for(int k=1;k<=b[i];k++){
				if(j>=w[g[i][k]]) f[j]=max(f[j],f[j-w[g[i][k]]]+v[g[i][k]]);
			}
		}
	}
	cout<<f[m];
	return 0;
}

二、 多重背包
多重背包类似01，但是就是区别是现在有n个物品，第i个物品有s[i]个。
（1）枚举取多少个
这个思路很简单，增加一层循环，for(k=0;k<=s[i];k++)
（2）多重背包转01背包
假设当前这个物品，重量为w，有s个
那么：
就把他假如一个数组中，在数组的末尾加入s个w，就相当于不把它看成一个物品来处理，把它看成s个物品来处理。
代码：

for(int j=1;j<=s;j++){
	w[++tot]=a[i];  //加入物品
}

一道例题：

砝码称重
题目描述

设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重<=1000），要求：计算用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况。
输入格式

一行，包括六个正整数a1,a2,a3,a4,a5,a6，表示1g砝码有a1个，2g砝码有a2个，……，20g砝码有a6个。相邻两个整数之间用单个空格隔开。
输出格式

以“Total=N”的形式输出，其中N为可以称出的不同重量的个数。
输入输出样列
输入样例1：

1 1 0 0 0 0

输出样例1：

Total=3

说明

【样例说明】

样例给出的砝码可以称出1g，2g，3g三种不同的重量。

写法1：
暴力

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

int g[10]={0,1,2,3,5,10,20};
int vis[10000010];

int main()
{


	int a,b,c,d,e,f;
	cin>>a>>b>>c>>d>>e>>f;
	for(int i=0;i<=a;i++){
		for(int j=0;j<=b;j++){
			for(int k=0;k<=c;k++){
				for(int l=0;l<=d;l++){
					for(int s=0;s<=e;s++){
						for(int o=0;o<=f;o++){
							int num=i*g[1]+j*g[2]+k*g[3]+l*g[4]+s*g[5]+o*g[6];
							vis[num]=1;
						}
					}
				}
			}
		}
	}
	int cnt=0;
	for(int i=1;i<=10000000;i++){
		if(vis[i]==1)cnt++;
	}
	cout<<"Total="<<cnt;


    return 0;
}

该问题是一个多重背包方案数问题，物品种类固定为6，每种物品有多个，背包也有多个，最小
为1，最大不超过1000。对于给定的砝码和砝码数量，求1-1000的背包中有哪些能被装满。
首先转换为 0-1背包，将数量为s的砝码，拆为s个数量为1的相同重量的砝码。
定义状态：d[i][j]表示使用前i个砝码凑刚好j的重量，是否能凑成功。
状态转移方程：对于砝码i有2种决策：
① 不使用第i个砝码，此时要用前i-1个砝码凑j的重量，d[i][j] = d[i-1][j]；
② 使用第i个砝码，此时要用前i-1个砝码凑j-w[i]的重量，d[i][j] = d[i-1][j-w[i]]；
上述2种方案只要有一种成立即可，即：d[i][j] = d[i-1][j] || d[i-1][j-w[i]];
滚动数组版本：d[j] = d[j] || d[j-w[i]];
代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

int w[1100],sum,tot,n,a[7]={0,1,2,3,5,10,20};
bool dp[1100];

int main()
{


	for(int i=1;i<=6;i++){
		int x;
		cin>>x;
		for(int j=1;j<=x;j++){
			w[++tot]=a[i];
			sum+=w[tot];
		}
	}
	//为了省事，用转01好一些
	dp[0]=1;
	for(int i=1;i<=tot;i++){
		for(int j=sum;j>=w[i];j--){
			dp[j]=dp[j]+dp[j-w[i]];
		}
	}
	int cnt=0;
	for(int i=1;i<=sum;i++){
		cnt+=dp[i];
	}
	printf("Total=%d",cnt);


    return 0;
}