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;
}