《最新pascal-采药-金明的预算方案详解.doc》由会员分享，可在线阅读，更多相关《最新pascal-采药-金明的预算方案详解.doc（31页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-datepascal-采药-金明的预算方案详解pascal-采药-金明的预算方案详解一. 动态规划相关算法及资料 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
3、 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);end;begin init; main; terminate;end.例题2 noip2006提高组 金明的预算方案 （有依赖的背包 or 分组背包）描述 Description 金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。
4、更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子： 主件 附件 电脑 打印机，扫描仪 书柜 图书 书桌 台灯，文具 工作椅 无 如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数15表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他
5、希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。 设第j件物品的价格为vj，重要度为wj，共选中了k件物品，编号依次为j1，j2，jk，则所求的总和为：vj1*wj1+vj2*wj2+ +vjk*wjk。（其中*为乘号）请你帮助金明设计一个满足要求的购物单。 输入格式 Input Format 输入文件的第1行，为两个正整数，用一个空格隔开： N m 其中N（32000）表示总钱数，m（60）为希望购买物品的个数。） 从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数 v p q （其中v表示该物品的价格（v0，表示该物品为附
6、件，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：这道题是一道典型的有依赖的背包问题，把一个主件看作是一个物品组，主件所属的附件为物品组中的物品，当枚举到每一组时，就有这样三种选择：这个物品组中一个物品都不要，即fj=maxfj-1,fj.:只要一个主件，
7、不要附件，即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,表示从一个未用未买主件k的f值，买主件k及附件b，得到fj的值。我们再为fj附加一个属性，用一个flag0.60+10,0.3200+10的数组，记录当价值为j时，是否买了主件k)主题代码：for 所有的组kfor 所有的i属于组k begin /处理是否要主件 for j:=n downto vk do if fjfj-vk+wk then
8、 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); assign(output,budget.out); reset(input); rewrite(output);end;procedure terminate;begin clo
9、se(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 begin inc(cq,0); cq,cq,0:=i; ci,0:=-1; end; end;end;procedure main;var i,j,k:longint;begi
10、n 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 do 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. -