1. 分组背包


题意

在01背包基础上,将其中的物体分成 $k$ 组,每组内的物品相互冲突,即只能取其中一个,问最大价值。


思路

同一组中各个物品是相互排斥的,那么我们对于处理可以外层循环组别,然后循环体积,最后循环组内的物品,然后套用01背包的转移方程 $dp[i]=max(dp[i],dp[i-v[k]]+w[k])$ 即可。我们来思考一下他的正确性,为什么只要这样循环就能确保每个组最多只取用一种呢?很明显组内的我们对于同一个体积 $V$ ,求体积 $V$ 对应的最大价值的时候,是从这个组内所有物品中取了能获得最大价值的策略,很明显当我们转移任何一个 $dp[i-v[k]]$ 的状态的时候,他们其中都不包含第 $i$ 组的物品,都是只包含了前 $i-1$ 组的物品,因为我们最终取得最大价值的路径是确定的,因此通过这个方式我们就可以确保每个组内只取一种,但是如果体积和组内物品的循环调换过来,就不行了,因为之前的状态就会包含当前组内的其他物品。


代码实现

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>

using namespace std;

const int maxn =1005;
const int maxt = 105; 
struct item
{
	int a,b;
}p[maxt][maxn];
int cnt[maxt];
int n,m;
int dp[maxn];
int q,w,e,maxe;
int main()
{
	scanf("%d%d",&m,&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&q,&w,&e);
		cnt[e]++;
		p[e][cnt[e]].a=q;
		p[e][cnt[e]].b=w;
		maxe=max(maxe,e);
	}
	for(int i=1;i<=maxe;i++)
	{
		for(int j=m;j>=0;j--)
		{
			for(int k=1;k<=cnt[i];k++)
			{
				if(j>=p[i][k].a)
				dp[j]=max(dp[j],dp[j-p[i][k].a]+p[i][k].b);
			}
		}
	}
	printf("%d",dp[m]);
} 

2. 有依赖的背包


题意

在01背包的基础上给物品加上依赖,某个物品可能为附件,必须买了主件之后才能买。规定一个物品最多有两个附件,并且附件不会再有附件,也不存在循环依赖(附件再依赖于主件)。问能获得的最大价值为多少。


思路

这道题有三种思路,难度依次递增。

  • 这道题的附件很少,可能为0,1,2。那么我们就在01背包的基础上,分五种情况来转移,分别是都不买,只买一个主件,只买主件和附件1,只买主件和附件2,买主件和两个附件。然后在这个基础上取一个最大的即可。但是这个思路对于附件可以很多的情况,就会特别麻烦。
  • 第二种思路是转化成分组背包,我们注意到对于每一个主件和附件的搭配都是唯一的,也就是每种方案都是互斥的。好比最多那五种情况,我们就可以分成一组。然后进行分组背包即可。那么我们分组的时候,可以考虑到一个优化,也就是如果他们的体积相同,我们只需要选价值大的那个就可以啦。所以我们先对主件和附件这个集合,进行01背包,然后背出来相同体积下最大价值的方案,分到对应组里。这个思路对于附件也有附件的情况,就不好写了,不能直接01背包。
  • 第三种思路可以应对附件也有附件的情况,可以用森林来表示所有物品之间的关系,然后树上dp做。然而,我不会。QAQ…

代码实现

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>

using namespace std;

const int maxn=32005;
const int maxm=65;
int n,m;
int num[maxm];
struct Item
{
	int v,p,q;
}item[maxm],minor[maxm][maxm];
int dp[maxn],cnt[maxm];
int vi[maxm][maxm],pi[maxm][maxm];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&item[i].v,&item[i].p,&item[i].q);
		if(item[i].q)
		{
			num[item[i].q]++;
			minor[item[i].q][num[item[i].q]].v=item[i].v;
			minor[item[i].q][num[item[i].q]].p=item[i].v*item[i].p;
		}
	}
	for(int i=1;i<=m;i++)
	{
		if(num[i])
		{
			memset(dp,-1,sizeof(dp));
			dp[0]=0;
			for(int j=1;j<=num[i];j++)
			{
				for(int k=n-item[i].v;k>=minor[i][j].v;k--)
				{
					if(dp[k-minor[i][j].v]!=-1)
					{
						dp[k]=max(dp[k],dp[k-minor[i][j].v]+minor[i][j].p);	
					}
				}
			}
			for(int k=0;k<=n-item[i].v;k++)
			{
				if(dp[k]!=-1)
				{
					cnt[i]++;
					vi[i][cnt[i]]=k+item[i].v;
					pi[i][cnt[i]]=dp[k]+item[i].v*item[i].p;
				}
			}
		}
		if(!item[i].q)
		{
			cnt[i]++;
			vi[i][cnt[i]]=item[i].v;
			pi[i][cnt[i]]=item[i].v*item[i].p;
		}
	}
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=m;i++)
	{
		if(!cnt[i]) continue;
		for(int j=n;j>=0;j--)
		{
			for(int k=1;k<=cnt[i];k++)
			{
				if(j>=vi[i][k])
				{
					dp[j]=max(dp[j],dp[j-vi[i][k]]+pi[i][k]);
				}
			}
		}
	}
//	int ans;
//	for(int i=1;i<=n;i++) ans=max(ans,dp[i]);
	printf("%d",dp[n]);
	return 0;
} 

3. 多米诺骨牌(隐式背包)


题意

多米诺骨牌有上下两个部分,分别具有一定点数。所有多米诺骨牌上部分点数之和与下部分点数之和差的绝对值为 $x$ ,多米诺骨牌可以进行上下翻转,问当 $x$ 最小的时候最少翻转几次。


思路

害,本来好像没有隐式背包这个说法,我自己瞎起的名字。。其实就是没那么裸的背包,实际上转化一下还是道背包的题。这道题本来其实看起来和背包没有什么关系,但是实际想一想,假如我们把所有多米诺骨牌一开始都调成上面大下面小的情况,然后调整过的把他的消耗值设为-1,没有调整过的把消耗值设为1。达成上大下小目的需要消耗的次数为n。调整后的上下点数差为V。我们每次调整之后 $V$ 会减少牌的上下点数之差,这就是我们需要的体积。然后一开始把 $dp[V]$ 设为n。然后转移方程为 $dp[i]=min(dp[i],dp[i+v[i]]+w[i]) $ 最后只需要求从 $0\sim V$ 最小的那个点数差对应的翻转次数值就可以了。


代码实现

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>

using namespace std;

const int maxn=1005;
int ini;
int n;
int up[maxn],down[maxn];
int v[maxn],w[maxn];
int dp[10005];
int V;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&up[i],&down[i]);
		if(up[i]>=down[i])
		{
			V+=up[i]-down[i];
			v[i]=(up[i]-down[i])*2;
			w[i]=1;
		}
		else
		{
			V+=down[i]-up[i];
			ini++;
			v[i]=(down[i]-up[i])*2;
			w[i]=-1;
		}
	}
	for(int i=0;i<=V;i++) dp[i]=233333;
//	dp[V]=ini;
	dp[V]=ini;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=V-v[i];j++)
		{
			if(dp[j+v[i]]!=233333)
			dp[j]=min(dp[j],dp[j+v[i]]+w[i]);
		}
	}
	for(int i=0;i<=V;i++)
	{
		if(dp[i]!=233333)
		{
			printf("%d",dp[i]); 
			break;
		}
	}
	return 0;
}