pascal采药金明的预算方案详解.doc

《pascal采药金明的预算方案详解.doc》由会员分享，可在线阅读，更多相关《pascal采药金明的预算方案详解.doc（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一. 动态规划相关算法及资料 1. 背包九讲二动归经典例题详解（标色解释：0 题目 0 类型 0 重要条件 0 解析）例题1.noip2005普及组 采药（01 背包） 描述 Description 辰辰是个天资聪颖孩子，他梦想是成为世界上最伟大医师。为此，他想拜附近最有威望医师为师。医师为了判断他资质，给他出了一个难题。医师把他带到一个到处都是草药山洞里对他说：“孩子，这个山洞里有一些不同草药，采每一株都需要一些时间，每一株也有它自身价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明孩子，你应该可以让采到草药总价值最大。” 如果你是辰辰，你能完成这个任务吗？ 输入格式

2、 Input Format 输入第一行有两个整数T（1 = T = 1000）和M（1 = M b) and (ac) then exit(c); if (ba) and (bc) then exit(b); exit(c);end;procedure main;var i,j,si,zi,t,m:longint;begin fillchar(f,sizeof(i),0); read(t,m); for i:=1 to m do begin read(si,zi); for j:=t downto si do fj:=max(fj,fj-si+zi,fj-1); end; writeln(ft

3、);end;begin init; main; terminate;end.例题2 noip2006提高组 金明预算方案 （有依赖背包 or 分组背包）描述 Description 金明今天很开心，家里购置新房就要领钥匙了，新房里有一间金明自己专用很宽敞房间。更让他高兴是，妈妈昨天对他说：“你房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买物品分为两类：主件与附件，附件是从属于某个主件，下表就是一些主件与附件例子： 主件 附件 电脑 打印机，扫描仪 书柜 图书 书桌 台灯，文具 工作椅 无 如果要买归类为附件物品，必须先买该附件所属主件。

4、每个主件可以有0个、1个或2个附件。附件不再有从属于自己附件。金明想买东西很多，肯定会超过妈妈限定N元。于是，他把每件物品规定了一个重要度，分为5等：用整数15表示，第5等最重要。他还从因特网上查到了每件物品价格（都是10元整数倍）。他希望在不超过N元（可以等于N元）前提下，使每件物品价格与重要度乘积总和最大。 设第j件物品价格为vj，重要度为wj，共选中了k件物品，编号依次为j1，j2，jk，则所求总和为：vj1*wj1+vj2*wj2+ +vjk*wjk。（其中*为乘号）请你帮助金明设计一个满足要求购物单。 输入格式 Input Format 输入文件第1行，为两个正整数，用一个空格隔开：

5、 N m 其中N（32000）表示总钱数，m（60）为希望购买物品个数。） 从第2行到第m+1行，第j行给出了编号为j-1物品基本数据，每行有3个非负整数 v p q （其中v表示该物品价格（v0，表示该物品为附件，q是所属主件编号） 输出格式 Output Format 输出文件只有一个正整数，为不超过总钱数物品价格与重要度乘积总和最大值 （200000）。 样例输入 Sample Input 1000 5800 2 0400 5 1300 5 1400 3 0500 2 0样例输出 Sample Output 2200时间限制 Time Limitation 1s Anasisi：这道题是

6、一道典型有依赖背包问题，把一个主件看作是一个物品组，主件所属附件为物品组中物品，当枚举到每一组时，就有这样三种选择：这个物品组中一个物品都不要，即fj=maxfj-1,fj.:只要一个主件，不要附件，即fj=maxfj,fj-vk+wk.(k为主件号)要附件，即fj=maxfj-vb+wb,fj-vb-vk+wk+wb,(b主件k一个附件，fj-vb+wb代表从一个已经买了主件f值，再买附件b,得到fj值；fj-vk-vb+vk+vb,表示从一个未用未买主件kf值，买主件k及附件b，得到fj值。我们再为fj附加一个属性，用一个flag0.60+10,0.3200+10数组，记录当价值为j时，是

7、否买了主件k)主题代码：for 所有组kfor 所有i属于组k begin /处理是否要主件 for j:=n downto vk do if fjfj-vk+wk then begin fj:=fj-vk+wk; flagk,j:=true; end; /处理附件 if fj=0,代表这是主件 f:array0.3200+10 of longint;/花费j元，可以得到最大价值 flag:array0.60+10,0.3200+10 of boolean;/花费j元得到最大价值，是否买了主件kprocedure init;begin assign(input,budget.in); assi

8、gn(output,budget.out); reset(input); rewrite(output);end;procedure terminate;begin close(input); close(output); halt;end;procedure readdata;var i,q:longint;begin read(n,m); n:=n div 10; /所有钱都整除10 fillchar(c,sizeof(c),0); for i:=1 to m do begin read(vi,wi,q); wi:=vi*wi; vi:=vi div 10; if q0 then begi

9、n inc(cq,0); cq,cq,0:=i; ci,0:=-1; end; end;end;procedure main;var i,j,k:longint;begin fillchar(f,sizeof(f),0); fillchar(flag,sizeof(flag),0); for k:=1 to m do if ck,0=0 then begin /处理只要主件情况 for j:=n downto vk do if fjfj-vk+wk then begin fj:=fj-vk+wk; flagk,j:=true; end; /处理买入附件情况 for i:=1 to ck,0 d

10、o for j:=n downto vck,i+vk do begin if fjfj-1 then fj:=fj-1; 这一句放在前面，可以避免出错。如果这三种情况得到f值相等，就要选第一种 if (not flagk,j-vk-vck,i) and (fjfj-vk-vck,i+wk+wck,i) then begin fj:=fj-vk-vck,i+wk+wck,i; flagk,j:=true; end; if (flagk,j-vck,i) and (fjfj-vck,i+wck,i) then begin fj:=fj-vck,i+wck,i; flagk,j:=true; end; end; end; writeln(fn);end;begin init; readdata; main; terminate;end.