本文为大型题解集

P2347 砝码称重 && P5020 货币系统
P1064 金明的预算方案

背包问题都可转化为 01 背包与分组背包问题。

P2347 砝码称重 && P5020 货币系统

对于给定砝码/货币求可凑成的重量/钱数，可将它们的重量/面额看作 $w$ 与 $c$ ，即费用与价值（ $w_i=c_i$ ）。创建 $m$ 个背包，从 $1$ 到 $m$ 扫一遍，若第 $i$ 个背包所装的物品价值为 $i$ ，即 $f_i=i$ ，则说明 $i$ 可以被凑成。

这两个题已有题解。

P1064 金明的预算方案

这题，刚看起来很难，因为要处理主件与附件的关系。其实，若运用分组的思想，这个题很容易。

对于这个题， $c$ 就是物品的价格与重要度的乘积， $w$ 就是物品的价格。

既然每个主件可以有 $0$ 个、 $1$ 个或 $2$ 个附件，则购买它们的情况分为 $4$ 种：

买一个主件。
买一个主件与一个附件。
买一个主件与另一个附件。
买一个主件与两个附件。

并且，在这些购买方案中，只能选一个。

这样，我们可以~~借鉴商场里的打包销售~~，把上面每种情况所涉及到的物品分别捆成一捆，当作 $4$ 个物品。这 $4$ 个物品中，要么只选一个，要么不选（分组！！！）。

设有 $q$ 个主件，则有 $q$ 组！

CODE：

#include<bits/stdc++.h> 
using namespace std;
int m,n,w[60][10],c[60][10],tol[60],f[32000+5]; 
int main()
{
	scanf("%d%d",&m,&n);
	for(int i=1;i<=n;i++)
	{
		int a,b,z;
		scanf("%d%d%d",&a,&b,&z);
		if(z==0)//主件
			w[i][1]=a,c[i][1]=a*b,tol[i]=1;
		else
			if(tol[z]==1)//第一个附件
				w[z][2]=a+w[z][1],c[z][2]=a*b+c[z][1],tol[z]=2;
			else//第二个附件
				w[z][3]=a+w[z][1],c[z][3]=a*b+c[z][1],w[z][4]=a+w[z][2],c[z][4]=a*b+c[z][2],tol[z]=4;
	}
	for(int i=1;i<=n;i++)//分组背包不用多说
		for(int j=m;j>=0;j--)
			for(int k=0;k<=tol[i];k++)
				if(j>=w[i][k])
					f[j]=max(f[j],f[j-w[i][k]]+c[i][k]);
		
	printf("%d",f[m]);
	return 0;
}