tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

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


一. 动态规划相关算法及资料 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 3 71 100 69 1 12 样例输出 Sample Output 3 Analysis:这是一道很裸的 01 背包入门题,用 f[j]表示花费时间 j 所能得到的最 大价值,s[i]表示第 i 个物品所花费的时间,w[i]表示第 i 个物品的价值,状态转 移方程为:f[j]=max{f[j-1],f[j-s[i]]+w[i]} For i:=1 to m do For j:=t downto s[i] do F[j]:=ma(f[j-1],f[j-s[i]]+w[i]); 最后,直接输出 f[t]即可。 var

f:array[0..1000+10] of longint;{典型的 01 背包; f[i]表示时刻 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 f[j]:=max(f[j],f[j-si]+zi,f[j-1]); end; writeln(f[t]); end; begin init; main; terminate;

end. 例题 2 noip2006 提高组 金明的预算方案 (有依赖的背包 or 分组背包) 描述 Description 金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间金明自 己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说: “你的房间需要购 买哪些物品,怎么布置,你说了算,只要不超过 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]。 (其中*为乘号)请你帮助金明设计一个满足要求的购物单。 输入格式 Input Format 输入文件的第 1 行,为两个正整数,用一个空格隔开: N m 其中 N(<32000)表示总钱数,m(<60)为希望购买物品的个数。 ) 从第 2 行到第 m+1 行,第 j 行给出了编号为 j-1 的物品的基本数据,每行有 3 个 非负整数 v p q (其中 v 表示该物品的价格(v<10000) 表示该物品的重要度(1~5) 表示 ,p ,q 该物品是主件还是附件。如果 q=0,表示该物品为主件,如果 q>0,表示该物品 为附件,q 是所属主件的编号) 输出格式 Output Format 输出文件只有一个正整数, 为不超过总钱数的物品的价格与重要度乘积的总 和的最大值 (<200000) 。 样例输入 Sample Input 1000 5 800 2 0

400 5 1 300 5 1 400 3 0 500 2 0 样例输出 Sample Output 2200 时间限制 Time Limitation 1s Anasisi: 这道题是一道典型的有依赖的背包问题, 把一个主件看作是一个物品组, 主件所属的附件为物品组中的物品,当枚举到每一组时,就有这样三种选择: ①:这个物品组中一个物品都不要,即 f[j]=max{f[j-1],f[j]}. ②:只要一个主件,不要附件,即 f[j]=max{f[j],f[j-v[k]]+w[k]}.(k 为主件号) ③要附件,即 f[j]=max{f[j-v[b]]+w[b],f[j-v[b]-v[k]]+w[k]+w[b]}, (b 主件 k 的一个附件,f[j-v[b]]+w[b]代表从一个已经买了主件的 f 值,再买附件 b,得到 f[j]的值; f[j-v[k]-v[b]]+v[k]+v[b],表示从一个未用未买主件 k 的 f 值, 买主 件 k 及 附 件 b , 得 到 f[j] 的 值 。 我 们 再 为 f[j] 附 加 一 个 属 性 , 用 一 个 flag[0..60+10,0..3200+10]的数组,记录当价值为 j 时,是否买了主件 k) 主题代码: for 所有的组 k for 所有的 i 属于组 k begin //处理是否要主件 for j:=n downto v[k] do if f[j]<f[j-v[k]]+w[k] then begin f[j]:=f[j-v[k]]+w[k]; flag[k,j]:=true; end; //处理附件 if f[j]<f[j-1] then f[j]:=f[j-1]; {这一句放在前面,可以避免出错。 如果三种情况得到的 f 值相等, 就要选这一种} F[j]:=max{f[j], f[j-v[b]]+w[b],f[j-v[b]-v[k]]+w[k]+w[b]}; end; 最后输出 f[n]即可。

var

n,m:longint; v,w:array[0..60+10] of longint; //记录每个物品的价格,价值 c:array[0..60+10,0..60+10] of longint;//用伪链表记录每个主件的附件,c[i,0]=-1 代表这是附件,c[i,0]>=0,代表这是主件 f:array[0..3200+10] of longint;//花费 j 元,可以得到的最大价值 flag:array[0..60+10,0..3200+10] of boolean;//花费 j 元得到最大价值, 是否买了主 件k procedure 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(v[i],w[i],q); w[i]:=v[i]*w[i]; v[i]:=v[i] div 10; if q<>0 then begin inc(c[q,0]); c[q,c[q,0]]:=i; c[i,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 c[k,0]>=0 then begin //处理只要主件的情况 for j:=n downto v[k] do if f[j]<f[j-v[k]]+w[k] then begin f[j]:=f[j-v[k]]+w[k]; flag[k,j]:=true; end; //处理买入附件的情况 for i:=1 to c[k,0] do for j:=n downto v[c[k,i]]+v[k] do begin if f[j]<f[j-1] then f[j]:=f[j-1]; {这一句放在前面,可以避免出错。 如果这三种情况得到的 f 值相等,就要选第一种} if (not flag[k,j-v[k]-v[c[k,i]]]) and (f[j]<f[j-v[k]-v[c[k,i]]]+w[k]+w[c[k,i]]) then begin f[j]:=f[j-v[k]-v[c[k,i]]]+w[k]+w[c[k,i]]; flag[k,j]:=true; end; if (flag[k,j-v[c[k,i]]]) and (f[j]<f[j-v[c[k,i]]]+w[c[k,i]]) then begin f[j]:=f[j-v[c[k,i]]]+w[c[k,i]]; flag[k,j]:=true; end; end; end; writeln(f[n]); end; begin init; readdata; main;

terminate; end.


推荐相关:

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

pascal 采药,金明的预算方案详解_学科竞赛_高中教育_教育专区。01背包与分组背包应用范例,如果对背包问题不甚明白,可参见背包九讲一...


NOIP2006提高组试卷

关于使用 Pascal 语言与编译结果的说明 1. 对于 Pascal 语言的程序, 当使用 ...【输入样例】 4 2 3 5 10 【输出样例】 710 2.金明的预算方案 (budget....


NOIP历年复赛提高组试题(2006-2014)

Pascal 语言与编译结果的说明 1.对于 Pascal 语言的...金明的预算方案(budget.pas/c/cpp) 【问题描述】...今天在课堂上, 老师讲解了如何求两个正整数 c1 和...


复赛试题

pascal 第7讲 递归与回溯 52页 免费如要投诉违规内容,请到百度文库投诉中心;如...【输入样例】 4 2 3 5 10 【输出样例】 710 2.金明的预算方案 . (...


NOIP复赛

关于使用 Pascal 语言与编译结果的说明 语言与 1.对于 Pascal 语言的程序,当...中国计算机学会,2006 2 NOIP 2006 复赛试题 (提高组) 2.金明的预算方案 . ...


noip集训练习 Day4

采药: 【问题描述】 辰辰是个天资聪颖的孩子,他的...7.金明的预算方案 NOIP2006 第二题 【问题描述】...long long (C/C++) 和 Int64 (Free Pascal)。 ...


NOIP2006普及组复赛试题PASCAL

NOIP2006普及组复赛试题PASCAL_工学_高等教育_教育专区...今天一早金明就开始做预算,但是他想买的东西太多了...999感冒灵市场营销方案 汽车品牌的足球世界杯营销 网...


动态规划47题

金明的预算方案 budget 第二十题 潜水员 gas 第...将会适合 long long(C/C++)和 Int64(Free Pascal...动态规划习题详解 32页 2下载券 动态规划题分析 4...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com