当前位置:编程学习 > C/C++ >>

hdu 1561 依赖背包

题意:n座城堡,每个里面都有宝物,要求在你可以攻占m个城堡得到的最多的宝物,但是如果要攻破一个城堡,必须要攻破它依赖的那个城堡,例如,如果a依赖b,那么如果想要攻破a就必须先攻破b。把每个城堡看作是物品,那么这个物品的城堡数量是1,价值就是宝物了。
解题思路:根据题意知道这种关系会形成一颗多叉树,根节点是0.从P=0开始,
1、遍历所有P的孩子,遇到某个孩子还有孩子,就把该节点当作P,继续1,直到遍历完所有的节点,如果P的所有孩子都没有孩子,那么转到2,存在有的孩子有孩子,转到3;
2、对P的所有孩子进行01背包,假设P的价值是Vp,P共有n个孩子,然后对每个孩子进行01背包(因为对于每个城堡只能取一次),那么可以得到城堡数量从0到n对应的最大价值(0对应的肯定是0了),用dp[i]表示,i代表城堡数量,dp[i]代表价值,接着从i=0开始,都加上P的价值Vp(因为所有的物品都依赖P),同时城堡的个数也加1;最后把得到的n+1个物品保存到P点,这样,这些物品就相当于分组背包里面的一组背包了,储存在castle里面,然后接着步骤1的遍历;
3、这个就很简单了,由于已经遍历过P所有孩子了,所以,只需要再从头开始遍历一遍所有孩子,如果遍历的孩子还有孩子,那么就把它的所有孩子当作是分组背包处理,如果遍历的孩子没有孩子,那么就当01背包处理,最后会得到一个城堡数量从0到m(也就是题目给的城堡数量的上限,以为不确定P的所有孩子的个数,所以就用最大的m)对应的最大价值,这个时候,如果P是0,那么就输出dp[m]就好了,如果不是,像2一样,dp[i]代表的价值都加上P的价值,数量也加1,也储存在castle里面,继续步骤1的遍历;
具体代码如下:
(提示:结构体s[i]代表城堡i的信息:num表示城堡的数量,value代表价值,key是自身的序号,depend代表i依赖的城堡编号;list castle[i]记录依赖i的城堡的信息)
[cpp] 
#include <cstdio> 
#include <string.h> 
#include <iostream> 
#include <list> 
 
using namespace std; 
#define N 205 
struct ss{ 
    int num,value,key,depend;//物品的个数,价值,自身的序号,依赖的序号; 
}s[N],one; 
list <ss> castle[N]; 
int dp[N],m; 
void fun(int n) 

    int num=0,i,j,k,minn; 
    list <ss>::iterator p,q; 
    p=castle[n].begin(); 
    while(p!=castle[n].end()) 
    { 
        if(castle[(*p).key].size()!=0) 
            fun((*p).key); 
        p++; 
    }    
    memset(dp,0,sizeof(dp)); 
    p=castle[n].begin(); 
    while(p!=castle[n].end()) 
    { 
        if(castle[(*p).key].size()!=0) 
        {            
            for(i=m;i>=0;i--) 
            { 
                q=castle[(*p).key].begin(); 
                while(q!=castle[(*p).key].end()) 
                { 
                    if(i-(*q).num>=0) 
                    dp[i]=max(dp[i],dp[i-(*q).num]+(*q).value); 
                    q++; 
                } 
            } 
        } 
        else 
        { 
            for(i=m;i>=(*p).num;i--) 
                dp[i]=max(dp[i],dp[i-(*p).num]+(*p).value); 
        } 
        p++; 
    } 
     
    castle[n].clear(); 
    if(!n) 
        cout<<dp[m]<<endl; 
    else 
    { 
        one.depend=n;one.key=n; 
        for(i=m;;i--) 
        { 
            if(dp[i]) 
            { 
                one.num=i+1;one.value=dp[i]+s[n].value; 
                castle[n].push_back(one); 
            } 
            else 
            { 
                one.num=1;one.value=s[n].value; 
                castle[n].push_back(one); 
                break; 
            } 
        } 
    } 
     

 
int main() 

    int n; 
    while(cin>>n>>m) 
    { 
        if(!n&&!m) 
            return 0; 
        int i,j,k,x; 
        for(i=0;i<=n;i++) 
            castle[i].clear(); 
        for(i=0;i<n;i++) 
        { 
            scanf("%d%d",&s[i+1].depend,&s[i+1].value); 
            s[i+1].num=1;   s[i+1].key=i+1; 
            castle[s[i+1].depend].push_back(s[i+1]); 
        } 
        fun(0);  
    } 

作者:jiang199235jiangJJ
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,