洛谷1064 金明的预算方案

Luogu

分析

这是一道经典的依赖背包问题,我们可以对应到分组背包来解决。
把主件与其附件集看成一个组,那么这个组会有5种选择:

  • 只选主件
  • 选主件和附件1
  • 选主件和附件2
  • 选主件和两个附件
  • 都不选

对于一些没有两个附件的主件,我们可以手动添加一个附件,其花费、重要度都为0。
这样就成功转化成了分组背包。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
int f[32001]; //f[i]表示前i组的最大价值  
int w[1000],c[1000]; //花费和价值 
int refer[1000]; //父节点 
int l[1000],r[1000]; //左右子树  
int a[1000][1000]; //a[i][j]表示第i组第j个物品的下标  
int main()
{
    int v,n;
    scanf("%d%d",&v,&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&w[i],&c[i],&refer[i]);
        c[i]*=w[i]; //价值=花费*重要度  
        if (refer[i]) //附件添加到主件集  
        {
            if (l[refer[i]]) r[refer[i]]=i;
            else l[refer[i]]=i;
        }
    }
    int t=0,p=n; //现在的物品组数、物品指针  
    for (int i=1;i<=n;i++)
    {
        if (!refer[i]) //是主件 
        {
            t++;
            a[t][0]=4; //除去不选有四种选择  
            a[t][1]=i; //只选主件  
            p++; w[p]=w[i]+w[l[i]]; c[p]=c[i]+c[l[i]]; a[t][2]=p; //主件和附件1  
            p++; w[p]=w[i]+w[r[i]]; c[p]=c[i]+c[r[i]]; a[t][3]=p; //主件和附件2  
            p++; w[p]=w[i]+w[l[i]]+w[r[i]]; c[p]=c[i]+c[l[i]]+c[r[i]]; a[t][4]=p; //都选  
        }
    }
    for (int k=1;k<=t;k++)
        for (int j=v;j>=0;j--)
            for (int i=1;i<=a[k][0];i++)
            {
                if (j>=w[a[k][i]])
                {
                    int tmp=a[k][i];
                    if (f[j]<f[j-w[tmp]]+c[tmp])
                        f[j]=f[j-w[tmp]]+c[tmp];
                }
            }
    printf("%d\n",f[v]); //输出  
    return 0;
}
最后修改:2019 年 09 月 23 日 10 : 05 PM

发表评论