ACMboy

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  4 Posts :: 0 Stories :: 0 Comments :: 0 Trackbacks

常用链接

留言簿

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

                                          金明的预算方案

                                             
金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过N元钱就行”。今天一早,金明就开始做预算了,他把想买的物品分为两类:主件与附件,附件是从属于某个主件的,下表就是一些主件与附件的例子:

主件

附件

电脑

打印机,扫描仪

书柜

图书

书桌

台灯,文具

工作椅

如果要买归类为附件的物品,必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多,肯定会超过妈妈限定的N元。于是,他把每件物品规定了一个重要度,分为5等:用整数1~5表示,第5等最重要。他还从因特网上查到了每件物品的价格(都是10元的整数倍)。他希望在不超过N元(可以等于N元)的前提下,使每件物品的价格与重要度的乘积的总和最大。

设第j件物品的价格为v[j],重要度为w[j],共选中了k件物品,编号依次为j1j2,……,jk,则所求的总和为:

v[j1]*w[j1]+v[j2]*w[j2]+ +v[jk]*w[jk]。(其中*为乘号)

请你帮助金明设计一个满足要求的购物单。

输入

1行,为两个正整数,用一个空格隔开:

N m

(其中N<32000)表示总钱数,m<60)为希望购买物品的个数。)

从第2行到第m+1行,j行给出了编号为j-1的物品的基本数据,每行有3个非负整数

v p q

(其中v表示该物品的价格(v<10000),p表示该物品的重要度(1~5),q表示该物品是主件还是附件。如果q=0,表示该物品为主件,如果q>0,表示该物品为附件,q是所属主件的编号)

输出

只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值(<200000)。

样例输入

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

样例输出

2200





#include 
<iostream>
const int Maxn=32000;
const int Maxm=60;
int maxvalue[Maxn][Maxm],Main[60];
int v[Maxm][3];
int w[Maxm][3],n,m;
int GetNeedMoney(int item,int idea)
{
    
int needmoney=0;
    
switch(idea)
    {
    
case 1:
        needmoney=w[item][0];
        
break;
    
case 2:
        needmoney=w[item][0]+w[item][1];
        
break;
    
case 3:
        needmoney=w[item][0]+w[item][2];
        
break;
    
case 4:
        needmoney=w[item][0]+w[item][1]+w[item][2];
        
break;
    
case 5:
        needmoney=0;
        
break;
    }
    
return needmoney;
}
int GetItemMaxValue(int money,int item,int idea)
{
    
int itemvalue=0;
    
if(money>=GetNeedMoney(item,idea))
    {
        
switch(idea)
        {
        
case 1:
            itemvalue=v[item][0];
            
break;
        
case 2:
            itemvalue=v[item][0]+v[item][1];
            
break;
        
case 3:
            itemvalue=v[item][0]+v[item][2];
            
break;
        
case 4:
            itemvalue=v[item][0]+v[item][1]+v[item][2];
            
break;
        
case 5:
            itemvalue=0;
            
break;
        }
    }
    
return itemvalue;
}
int GetMaxValue(int money,int item)
{
    
int &ans=maxvalue[money][item];
    
int max=0,tmp;
    
if(ans!=-1)
    {
        
return ans;    
    }
    
if(item==1)
    {
        
for(int j=1;j<=5;j++)
        {
            tmp=GetItemMaxValue(money,item,j);
            
if(max<tmp)
                max=tmp;
        }
    }
    
else  
        
        
for(int i=1;i<=5;i++)
        {
            
int usedmoney=GetNeedMoney(item,i);
            
if(money>=usedmoney)
            {
                tmp=GetItemMaxValue(usedmoney,item,i)+GetMaxValue(money-usedmoney,item-1);
                
if(max<tmp)
                    max=tmp;
            }
        }
        
return ans=max;
}
int main()
{
    
int value,p,q,MaxItem=0;
    memset(maxvalue,-1,
sizeof(maxvalue));
    memset(v,0,
sizeof(v));
    scanf("%d%d",&m,&n);
    
for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&value,&p,&q);
        
if(q==0)
        {
            ++MaxItem;    
            v[MaxItem][0]=value*p;
            w[MaxItem][0]=value;
            Main[i]=MaxItem;
        }
        
else
        {              
            
int MainOrder=Main[q];
            
if(v[MainOrder][1]==0)
            {
                v[MainOrder][1]=value*p;
                w[MainOrder][1]=value;
            }
            
else
            {
                v[MainOrder][2]=value*p;
                w[MainOrder][2]=value;
            }
        }
    }
    n=MaxItem;
    printf("%d\n",GetMaxValue(m,n));
    
return 0;
}

posted on 2010-04-06 22:55 EG-HUA 阅读(971) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理