pascal采药金明的预算方案详解.doc
一. 动态规划相关算法及资料 1. 背包九讲二动归经典例题详解（标色解释：0 题目 0 类型 0 重要条件 0 解析）例题1.noip2005普及组 采药（01 背包） 描述 Description 辰辰是个天资聪颖孩子，他梦想是成为世界上最伟大医师。为此，他想拜附近最有威望医师为师。医师为了判断他资质，给他出了一个难题。医师把他带到一个到处都是草药山洞里对他说：“孩子，这个山洞里有一些不同草药，采每一株都需要一些时间，每一株也有它自身价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明孩子，你应该可以让采到草药总价值最大。” 如果你是辰辰，你能完成这个任务吗？ 输入格式 Input Format 输入第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），用一个空格隔开，T代表总共能够用来采药时间，M代表山洞里草药数目。接下来M行每行包括两个在1到100之间（包括1和100）整数，分别表示采摘某株草药时间和这株草药价值。 输出格式 Output Format 输出包括一行，这一行只包含一个整数，表示在规定时间内，可以采到草药最大总价值。 样例输入 Sample Input 70 371 10069 11 2样例输出 Sample Output 3 Analysis：这是一道很裸01背包入门题，用fj表示花费时间j所能得到最大价值，si表示第i个物品所花费时间，wi表示第i个物品价值，状态转移方程为：fj=maxfj-1,fj-si+wi For i:=1 to m do For j:=t downto si do Fj:=ma(fj-1,fj-si+wi);最后，直接输出ft即可。var f:array0.1000+10 of longint;典型01背包； fi表示时刻i所能得到最大价值, 枚举时必须从大往小。procedure init;begin assign(input,'noip2005.in'); assign(output,'noip2005.out'); reset(input); rewrite(output);end;procedure terminate;begin close(input); close(output); halt;end;function max(a,b,c:longint):longint;begin if (a>b) and (a>c) then exit(c); if (b>a) and (b>c) 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);end;begin init; main; terminate;end.例题2 noip2006提高组 金明预算方案 （有依赖背包 or 分组背包）描述 Description 金明今天很开心，家里购置新房就要领钥匙了，新房里有一间金明自己专用很宽敞房间。更让他高兴是，妈妈昨天对他说：“你房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买物品分为两类：主件与附件，附件是从属于某个主件，下表就是一些主件与附件例子： 主件 附件 电脑 打印机，扫描仪 书柜 图书 书桌 台灯，文具 工作椅 无 如果要买归类为附件物品，必须先买该附件所属主件。每个主件可以有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行，为两个正整数，用一个空格隔开： N m 其中N（<32000）表示总钱数，m（<60）为希望购买物品个数。） 从第2行到第m+1行，第j行给出了编号为j-1物品基本数据，每行有3个非负整数 v p q （其中v表示该物品价格（v<10000），p表示该物品重要度（15），q表示该物品是主件还是附件。如果q=0，表示该物品为主件，如果q>0，表示该物品为附件，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.:只要一个主件，不要附件，即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时，是否买了主件k)主题代码：for 所有组kfor 所有i属于组k begin /处理是否要主件 for j:=n downto vk do if fj<fj-vk+wk then begin fj:=fj-vk+wk; flagk,j:=true; end; /处理附件 if fj<fj-1 then fj:=fj-1; 这一句放在前面，可以避免出错。 如果三种情况得到f值相等，就要选这一种 Fj:=maxfj, fj-vb+wb,fj-vb-vk+wk+wb; end; 最后输出fn即可。var n,m:longint; v,w:array0.60+10 of longint; /记录每个物品价格，价值 c:array0.60+10,0.60+10 of longint;/用伪链表记录每个主件附件，ci,0=-1代表这是附件，ci,0>=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 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 q<>0 then begin 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 fj<fj-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 fj<fj-1 then fj:=fj-1; 这一句放在前面，可以避免出错。如果这三种情况得到f值相等，就要选第一种 if (not flagk,j-vk-vck,i) and (fj<fj-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 (fj<fj-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.
