当前位置:首页 >> 学科竞赛 >>

NOIP2006提高组budget金明的预算方案


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

主件与附件的例子: 主件 电脑 书柜 书桌 附件 打印机,扫描仪 图书 台灯,文具

工作椅 无 如果要买归类为附件的物品,必须先买该附件所属的主件。每个主件可以有 0 个、1 个或 2 个附件。附件 不再有从属于自己的附件。金明想买的东西很多,肯定会超过妈妈限定的 n 元。于是,他把每件物品规定了一 个重要度,分为 5 等:用整数 1~5 表示,第 5 等最重要。他还从因特网上查到了每件物品的价格(都是 10 元的 整数倍)。他希望在不超过 n 元(可以等于 n 元)的前提下,使每件物品的价格与重要度的乘积的总和最大。 设第 j 件物品的价格为 v[j],重要度为 w[j],共选中了 k 件物品,编号依次为 j1,j2,……,jk,则所求 的总和为: v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。(其中*为乘号) 请你帮助金明设计一个满足要求的购物单。 【输入文件】 输入文件 budget.in 的第 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 是所属主件的编号) 【输出文件】 输出文件 budget.out 只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值 (<200000)。 【输入样例】 1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0 【输出样例】 2200

- 1 -

2009-06-03

NOIP2006 提高组 budget 金明的预算方案
DP:有利润的背包问题,可以先把主件和附件的搭配全部分出来,然后分阶段做背包,O(mn/10) program budget;{第 18 届国际信息学奥林匹克竞赛金牌获得学生复旦附中高三李天翼 noip2006} const maxm=32000;maxn=60; var a,b:array [0..maxm] of longint; c,w,q,u:array [1..maxn] of longint; n,m,i,j,tem:longint; begin assign(input,'budget.in');reset(input); assign(output,'budget.ans');rewrite(output); readln(m,n); for i:=1 to n do readln(c[i],w[i],q[i]); {物品的价格,物品的重要度,物品是(0 主件,>0 附件所属主件的编号)} for i:=1 to n do w[i]:=w[i]*c[i]; {物品的重要度*价格?物品的重要度} for i:=1 to n do if q[i]=0 then {如果是物品的主件,u[i]=0,标志第 i 个主件没有附件,q[i]= i,标志第 i 个主件没有附件} begin u[i]:=0;q[i]:=i end else u[i]:=1; {如果是物品的附件,u[i]=1,标志第 i 个主件含有附件,q[i]=初始值,所属主件的编号}
{下面两重循环排序:没有附件的物品按照读入顺序升序排列,如果读入顺序值=该附件物品所属主件的编号,则有附件的排后面}

for i:=1 to n-1 do for j:=1 to n-1 do if (q[j]>q[j+1])or(q[j]=q[j+1])and(u[j]>u[j+1])then
{如果 (q[j]>q[j+1]) 或者第 j 个附件物品所属主件的编号正好=第 j+1 个读入顺序值 q[i]= i,则由语句(u[j]>u[j+1]) 判断哪个含有附件的升序排列在后面}

begin tem:=c[j];c[j]:=c[j+1];c[j+1]:=tem; tem:=w[j];w[j]:=w[j+1];w[j+1]:=tem; tem:=q[j];q[j]:=q[j+1];q[j+1]:=tem; tem:=u[j];u[j]:=u[j+1];u[j+1]:=tem end; for i:=0 to m do a[i]:=-maxlongint; fillchar(b,sizeof(b),0); for i:=1 to n do if u[i]=1 then{含有附件的背包问题} for j:=m downto c[i] do{m 总钱数,c[i]第 i 个物品的价格} begin tem:=a[j-c[i]]+w[i]; if tem>a[j] then a[j]:=tem{当用钱数相同时,选择物品重要度*价格高的,w[i] =物品的重要度*价格} end else{没有附件的背包问题} begin for j:=m downto 0 do if a[j]>b[j] then b[j]:=a[j];
{b 数组初值=0,a 数组初值=-maxlongint,已处理过的含有附件的物品一定>b 数组对应单元,存放?b 数组}

for j:=m downto c[i] do a[j]:=b[j-c[i]]+w[i];
{w[i] =物品的重要度*价格,含有附件的物品已处理过?b 数组}

for j:=c[i]-1 downto 0 do a[j]:=-maxlongint{含有附件的物品已处理过?b 数组} end; if a[m]>b[m] then writeln(a[m]) else writeln(b[m]); close(input);close(output)

- 2 -

2009-06-03

NOIP2006 提高组 budget 金明的预算方案
end.

- 3 -

2009-06-03


相关文章:
NOIP2006提高组budget金明的预算方案
NOIP2006提高组budget金明的预算方案_学科竞赛_高中教育_教育专区。NOIP2006 提高组 budget 金明的预算方案【问题描述】 金明今天很开心,家里购置的新房就要领钥匙...
NOIP2006 senior budget金明的预算方案_题目
NOIP2006 senior budget 金明的预算方案_题目【问题描述】 金明今天很开心,家...NOIP2006提高组budget金... 3页 免费 noip2006金明的预算方案... 6页 ...
noip2006金明的预算方案 个人题解
noip2006金明的预算方案 个人题解_IT/计算机_专业资料。金明的预算方案 (budget...NOIP2006提高组budget金... 3页 免费 预算编制方案(2) 2页 免费 资金预算方...
《金明的预算方案》三种解法
不同解法湖北省襄樊市第五中学 杨兵 《金明的预算方案》是 NOIP2006 提高组的...参考代码如下: program budget; var a:array[1..60,0..3] of integer;/...
NOIP2006 提高组试题
中国计算机学会,2006 2 NOIP 2006 复赛试题 (提高组) 2.金明的预算方案 . (budget.pas/c/cpp) 【问题描述】 金明今天很开心, 家里购置的新房就要领钥匙了...
NOIP2006提高组试卷
第十二届全国青少年信息学奥林匹克 联赛复赛试题(NOIP2006 提高组) 竞赛时间:...【输入样例】 4 2 3 5 10 【输出样例】 710 2.金明的预算方案 (budget....
noip2006提高组解题报告及源程序
noip2006提高组解题报告及源程序_IT/计算机_专业资料。06NOIP2006 Solutions 2006...问题二 金明的预算方案/Budget 金明的预算方案 核心算法 动态规划 (原型 0-1...
pascal 采药,金明的预算方案详解
例题 2 noip2006 提高组 金明的预算方案 (有依赖的背包 or 分组背包) 描述 ...(input,'budget.in'); assign(output,'budget.out'); reset(input); ...
NOIP2006和2010提高组复赛命题与解题报告
NOIP2006和2010提高组复赛命题与解题报告_初三英语_英语_初中教育_教育专区。NOIP...2.金明的预算方案(budget.pas/c/cpp) .金明的预算方案 【问题描述】 金明...
NOIP历年复赛提高组试题(2006-2014)
2006~2014 年 NOIP 复赛试题集(提高组) 第十二届全国信息学奥林匹克分区联赛(...【输入样例】 4 2 3 5 【输出样例】 710 10 2.金明的预算方案(budget....
更多相关标签:
预算 决算 budget | 金明的预算方案 | noip2006 | noip2006普及组复赛 | noip2006提高组 | noip2006能量项链 | noip2006提高组初赛 | noip2006普及组初赛 |