当前位置:首页 >> 其它 >>

noip讲义7-穷举法


穷举法
在程序设计中,我们经常需要根据给定的一组条件求满足 条件的解。如果问题的解可以用公式,或者按一定的规则、规 律求出,那么就可以很容易地写出相应的程序。但是对于许多 问题,我们都难以找到明确的公式和计算规则,在这种情况下, 我们可以利用计算机高速运算的特点,用穷举法来求解。
基本思想: 穷举也叫枚举,它的基本思想是先依据题目的部分条件将 所有可能解列举出来,然后用其余的条件对所有可能解进行一 一验证,删去那些不符合条件的解,剩下符合条件的解就是整 个问题的解。 适用枚举法求解的问题必须满足两个条件: 1、可事先确定解元素的个数n; 2、解变量A1,A2,…,An的可能值为一个连续的 值域。

例1、 1995年复赛题
设有下列的除法算式: 本题已给出了商 和余数,只要再知道 被除数或除数,就可 确定整个算式。枚举 除数枚举量较小,我 们选择枚举除数,而 被除数则可按公式 y=809*x+1计算得出。

我们不可能对14个格子 中的数都进行枚举,本题的 关键在于找出适当的元素进 行枚举。

请根据上述算式中的信息求出被除数和除数。

其它信息: 设除数为x,被除数为y,则10<=x<=99,1000<=y<=9999,且8*x<=99, 9*x>=100。

穷举法是一种比较笨拙的算法,因为它需要列举出许多个可能解来一一验证,程 序往往需要运行很长时间,效率较低。 针对穷举法效率较低的缺点,在设计穷举算法时,我们必须注意以下二点: ①减少枚举变量:充分挖掘各解元素之间的联系,将一些非枚举不可的解元素列 为枚举变量,然后在此基础上直接计算出其它解元素的可能值。 ②减少枚举变量的值域:枚举前要尽可能多地将不符合条件的情况预先排除。

var x,y:integer; 枚举所有可能的除数 begin for x:=10 to 99 do begin y:=( 809*x+1 ); {计算出被除数} if y>9999 then break;{优化语句} 验证 if ( (y>=1000) and (8*x<=99) and (9*x>=100) then writeln(y,' ',x); end; end. 运行结果: 9709 12



例2、数字分组(1998年普及组复赛第一题) 将1,2...9共9个数分成三组,分别组成三个三位数,且使 这三个三位数构成1:2:3的比例,试求出所有满足条件的三个 三位数。 例如:三个三位数192,384,576满足以上条件。 分析: 确定最小的三位数i为枚举变量,枚举范围是123<=i<=329, 则另外二个三位数为2*i和3*i。接着分别求出组成这三个三位 数的9个数字进行验证,如果这9个数字刚好是1到9的9个数字, 则i,2*i,3*i即为解。

var i,j,s:integer; 枚举123到329之 a:array[1..9] of 0..1; {标记数字j有没有出现} 间的所有三位数 begin for i:=123 to 329 do begin for j:=1 to 9 do a[j]:=0; a[i div 100]:=1; a[i div 10 mod 10]:=1; a[i mod 10]:=1; 分别找出组 a[2*i div 100]:=1; 成这三个三 a[2*i div 10 mod 10]:=1; 位数的9个 a[2*i mod 10]:=1; a[3*i div 100]:=1; 数字。 a[3*i div 10 mod 10]:=1; a[3*i mod 10]:=1; s:=0; for j:=1 to 9 do s:=s+a[j]; 验证 if s=9 then writeln(i:4,2*i:4,3*i:4); end; end.

例3:方格填数
如下图所示的八个格子中填入1至8八个数字,使得相邻的 和对角线的数字之差不为1。请编程找出所有放法。
b1 b2 b5 b3 b6 b4 b7

b8
分析: 由题意可知,放入b3,b6这两个格子中的数,必须和六个数不连续,仅 可以和一个数是连续的,这样的数只能是1和8。因此,b1,b3,b6,b8这四 个格子中数的放法可以先确定下来:2,8,1,7或7,1,8,2。接着,我们 只需枚举b2、b4、b5三个变量,范围都是3至6,而b7可通过计算来得到。 (1,2),(1,4),(2,5),(4,7),(5,8),(7,8)共6对格子中的数需要验证。

const link:array[1..6,1..2] of integer=((1,2),(1,4),(2,5),(4,7),(5,8),(7,8)); var b:array[1..8] of integer;{存放摆放方案} procedure print; {输出一种满足条件的放法} begin writeln(b[1]:4); writeln(b[2]:2,b[3]:2,b[4]:2); writeln(b[5]:2,b[6]:2,b[7]:2); writeln(b[8]:4); writeln; end; function choose:boolean; {检验当前放法是否符合要求} var i:integer; begin choose:=false; for i:=1 to 6 do if abs( b[link[i,1]] - b[link[i,2]] )=1 then exit; choose:=true; end;

procedure try; begin for b[2]:=3 to 6 do {枚举b[2],b[4],b[5],计算b[7]} for b[4]:=3 to 6 do if b[2]<>b[4] then for b[5]:=3 to 6 do if (b[5]<>b[2])and(b[5]<>b[4]) then begin b[7]:=18-b[2]-b[4]-b[5]; if choose then print; end; end; begin b[1]:=2; b[3]:=8; b[6]:=1; b[8]:=7;{情况一} try; b[1]:=7; b[3]:=1; b[6]:=8; b[8]:=2;{情况二} try; readln; end.

例4、数字三角形 (1998年普及组复赛第二题) 将1,2,··,9共9个数排成下列形态的三角形。 ·· ·· a b c d e f g h i

其中:a~i分别表示1,2,··,9中的一个数字,并要求同时满足下 ·· ·· 列条件: (1)a<f<i; (2)b<d, g<h, c<e; (3)a+b+d+f=f+g+h+i=i+e+c+a=P; 程序要求:根据输入的边长之和P,输出所有满足上述条件的三角形 的个数。 分析:此题只要根据题目条件逐个枚举三角形每条边上的某些变量即 可得到问题的解。由于每条边上的和为定值P,因此每条边上均可少枚举 一个变量,余下的变量的值可以通过计算得出。另外,三个角上的变量被 两条边共用,应首先被枚举,并且由题意可知三个角上的变量a,f,i之和 为3P-45,只需枚举a、f即可,i可通过计算得到。综上所述,本题总共需 要枚举的变量个数为5个,即:a,f,b,g,c。

var a,b,c,d,e,f,g,h,i,p,ans:integer; s:set of 1..9;{s是一个集合类型变量} begin readln(p); ans:=0; for a:=1 to 7 do {枚举a、 f,计算i} for f:=a+1 to 8 do begin s:=[1..9]; i:=3*p-45-a-f; if i>f then begin s:=s-[a,f,i]; for b:=1 to 8 do if ( b in s ) and (( p-a-b-f ) in s ) and ( p-a-b-f>b ) then for g:=1 to 8 do if ( g in s ) and (( p-f-g-i ) in s ) and ( p-f-g-i>g ) then for c:=1 to 8 do if ( c in s ) and (( p-a-c-i ) in s ) and ( p-a-c-i>c )

then begin 输入:20 d:=p-a-b-f; 输出:6 h:=p-f-g-i; e:=p-a-c-i; s:=s-[b,d,g,h,e,c]; 验证 if s=[] then ans:=ans+1; s:=[1..9]-[a,f,i]; end; end; end; writeln(ans);{输出方案总数} end.

输入文件jzzh.in:输入的每行有两个输入数据。第一个是十进 制数N(-32768<=N<=32767);第二个是负进制数的 基数-R。 输出文件jzzh.out:输出此负进制数,若基数超过10,则参照 例5、进制转换 16进制的方式处理。 样例: 我们可以用这样的方式来表示一个十进制数: 将每个阿拉伯数字乘以一个以该 输入1 数字所处位置的值减1为指数,以10为底数的幂之和的形式。例如:123可表示为 30000 -2 1*102+2*101+3*100这样的形式。与之相似的,对二进制数来说,也可表示 输出1 成每个二进制数码乘以一个以该数字所处位置的值减1为指数,以2为底数的幂之 11011010101110000 和的形式。一般说来,任何一个正整数R或一个负整数-R都可以被选来作为一个 输入2 数制系统的基数。如果是以R或-R为基数,则需要用到的数码为0, -25000 -16 1,....R-1。例如,当R=7时,所需用到的数码是0,1,2,3,4,5和6,这 输出2 与其是R或-R无关。如果作为基数的数绝对值超过10,则为了表示这些数码,通 7FB8 常使用英文字母来表示那些大于9的数码。例如对16进制数来说,用A表示10,
用B表示11,用C表示12,用D表示13,用E表示14,用F表示15。 在负进制数中是用-R作为基数,例如-15(十进制)相当于110001 -32768<=N<=32767,用穷举法完全可以解决问题.穷举时只需 (-2进制),并且它可以被表示为2的幂级数的和数: 从0开始逐一穷举-R进制数,又对被穷举的-R进制数算出其对应的十进 110001=1*(-2)5+1*(-2)4+0*(-2)3+0*(-2) 2+0*(-2)1 +1*(-2)0 制值,若该值等于N,则输出该-R进制数,结束程序,否则重复考察下一个设计一个程序,读入一个十进制数和一个负进制数的基数, 并将此十进制数转 R进制数,直到找到要求的-R进制数为止. 换为此负进制下的数:-R∈{-2,-3,-4,...,-20}

var i,m,n,r,s:longint; a:array[1..100] of longint;{保存-R进制数} begin readln(n,r); r:=-r; m:=1;{记录位数} for i:=1 to 100 do a[i]:=0; a[1]:=-1; repeat a[1]:=a[1]+1 ;{从0开始逐一穷举-R进制数} i:=1; {处理进位} while a[i]=r do begin a[i]:=0; i:=i+1; a[i]:=a[i]+1 end; if i>=m then m:=i;{修正位数} s:=0; for i:=m downto 1 do s:=s*(-r)+a[i]{算出对应的十进制数} until n=s; for i:=m downto 1 do if a[i]<=9 then write(a[i]) else write(chr(a[i]+55)); end.

例6、比赛安排
设有有2 n(n<=6)个球队进行单循环比赛,计划在2 n – 1 天内完成,每个队每天进行一场比赛。设计一个比赛的安排,使 在2 n – 1天内每个队都与不同的对手比赛。 例如n=2时的比赛安排: 队 1 2 3 4 比赛 1==2 3==4 一天 1==3 2==4 二天 1==4 2==3 三天

const maxn=64; var a:array[1..maxn,1..maxn] of boolean; b:array[1..maxn] of boolean; n,d,i,j:integer; begin readln(n); n:=round(exp(ln(2)*n)); {求2n} fillchar(a,sizeof(a),0); for d:=1 to n-1 do {枚举每一天} begin fillchar(b,sizeof(b),0); write(‘(’,d,‘)’);{输出天数} for i:=1 to n do {枚举每一球队} if not b[i] then begin{若在第d天还未安排比赛} b[i]:=true; {则为其安排比赛} write(i); 在这天还未参加比赛过的其它球队 for j:=1 to n do 中找一个还未曾与i比赛过的球队j if not b[j] and not a[i,j] then break; write(‘==’,j,‘ ’);{i与j比赛} b[j]:=true; a[i,j]:=true; a[j,i]:=true end; writeln end end.

例7、 2001年初赛题
在A、B两个城市之间设有N个路站(如下图中的S1,且N<100),城市 与路站之间、路站和路站之间各有若干条路段(各路段数<=20,且每条路 段上的距离均为一个整数)。 A,B的一条通路是指:从A出发,可经过任一路段到达S1,再从S1 出发经过任一路段,…最后到达B。通路上路段距离之和称为通路距离(最 大距离<=1000)。当所有的路段距离给出之后,求出所有不同距离的通路 个数(相同距离仅记一次)。 例如:下图所示是当N=1时的情况:

从A到B的通路条数为6,但因其中通路5+5=4+6,所以满足条件的不 同距离的通路条数为5。 数据结构: N记录A,B间路站的个数; 数组D[i,0]记录第i-1个到第i个路站间路段的个数; D[i,1],D[i,2],…,记录每个路段的距离; 数组G记录可取到的距离。

8 6 b[0] 0 0 0 0 0 0 0 0 0 0 0 0 1 b[1] 1 1 1 1 1 1 2 2 2 2 2 2 1

4 5 7 b[2] 1 1 2 2 3 3 1 1 2 2 3 3 1

3 4

D[1,0]=2, D[1,1]=8, D[1,2]=6 D[2,0]=3, D[2,1]=4, D[2,2]=5,D[2,3]=7 D[3,0]=2, D[3,1]=3, D[3,2]=4

b[3] 1 2 1 2 1 2 1 2 1 2 1 2 1

8+4+3=15 8+4+4=16 8+5+3=16 8+5+4=17 8+7+3=18 8+7+4=19 6+4+3=13 6+4+4=14 6+5+3=14 6+5+4=15 6+7+3=16 6+7+4=17 穷举结束

g[15]=1 g[16]=1 g[16]=1 g[17]=1 g[18]=1 g[19]=1 g[13]=1 g[14]=1 g[14]=1 g[15]=1 g[16]=1 g[17]=1

var 穷举用 i,j,n,s:integer; while( b[0]<>1)do 求当前通 路的距离 b:array[0..100] of integer; begin d:array[0..100,0..20] of integer; s:=0; g:array[0..1000] of 0..1; for i:=1 to n+1 do begin s:=( s+d[ i , b[i] ] ); readln(n); g[s]:=1; 产生一种 作记录 for i:=1 to n+1 do j:=n+1; 新的方案 begin while( b[j]=d[j,0] )do j:=j-1; readln(d[i,0]); b[j]:=b[j]+1; for j:=1 to d[i,0] do for i:=j+1 to n+1 do b[i]:=1; read(d[i,j]); end; end; s:=0; 循环开关 d[0,0]:=1; for i:=1 to 1000 do( s:=s+g[i] ); for i:=1 to n+1 do b[i]:=1; writeln(s); 统计不同的 b[0]:=0; readln; 通路条数 for i:=1 to 1000 do g[i]:=0; end.

例8、 2000年初赛题
将2n个0和2n个1,排成一圈。从任一个位置开始,每次按逆时针的方向 以长度为n+1的单位进行数二进制数。要求给出一种排法,用上面的方法产 生出来的2n+1个二进制数都不相同。例如,当n=2时,即22个0和22个1排成如 下一圈:

比如,从A位置开始,逆时针方向取三个数000,然后再从B位置上开始 取三个数001,接着从C开始取三个数010,...可以得到000,001,010,101, 000 001 010 011 100 101 110 111 011,111,110,100共8个二进制数且都不相同。 5 0 1 2 3 4 6 7
程序说明:

以n=4为例,即有16个0,16个1,数组a用以记录32个0,1的排法,数 组b统计二进制数出现的可能性。

0 0 0 0 0 a[6]

a[27] 1 1 1 1 1

1000000000000000000000 1000000000000000000001 1000000000000000000010 1000000000000000000011 1000000000000000000100 1000000000000000000101 1000000000000000000110 1000000000000000000111 1000000000000000001000 1000000000000000001001 1000000000000000001010

while ( p=1 ) do var begin a:array[1..36] of 0..1; 循环开关 j:=27 b:array[0..31] of integer; while a[j]=1 do j:=j-1; i,j,k,s,p:integer; 产生一种 ( a[j]:=1 ) begin 新的方案 for i:=j+1 to 27 do ( a[i]:=0 ) for i:=1 to 36 do a[i]:=0; for i:=0 to 31 do b[i]:=0; for i:=28 to 32 do a[i]:=1; for i:=1 to 32 do 转化为10 p:=1; begin a[6]:=1; 进制数 ( s:=0 ) S=0*2+1=1 for k:=i to i+4 do S=1*2+1=3

11011

S=3*2+0=6 S=6*2+1=13 S=13*2+1=27

for i:=1 to 32 do for j:=i to i+4 do write(a[j]); writeln end.

s:=s*2+a[k]; 作记录 ( b[s]:=1 ) end; 统计个数 s:=0; for i:=0 to 31 do s:=s+b[i]; if ( s=32 ) then p:=0 end;

例9、 2002年初赛题
将n个整数分成k组(k≤n,要求每组不能为空),显然这k个部分均可得 到一个各自的和s1,s2,……,sk,定义整数P为:

P=(S1-S2)2+(S1一S3)2+……+(S1-Sk)2+(s2-s3)2+……+(Sk-1-Sk)2
问题求解: 求出一种分法,使P为最小(若有多种方案仅记一种〉。

程序说明:
数组:a[1],a[2],...a[n]存放原数 s[1],s[2],...,s[k]存放每个部分的和 b[1],b[2],...,b[n]穷举用临时空间 d[1],d[2],...,d[n]存放最佳方案

var i,j,n,k : integer; 打擂台 a :array [1..100] of integer; b,d:array [0..100] of integer; s :array[1..30] of integer; begin readln(n,k); for i:=1 to n do read(a[i]); 分组初 始化 for i:=0 to n do b[i]:=1; cmin:=1000000; 循环开关 while (b[0]=1) do begin for i:=1 to k do ( s[i]:=0 );
for i:=1 to n do( s[b[i]]:=s[b[i]]+a[i] );

if( cmin>sum )then

begin
cmin:=sum;
for i:=1 to n do d[i]:=b[i];

end; j:=n; b[j]:=b[j]+1;

产生一种 新的方案

while( b[j]=k )j:=j-1;
for i:=j+1 to n do( b[i]:=1) end; writeln(cmin); for i:=1 to n write(d[i]:40);

sum:=0; for i:=1 to k-1 do for j:=( i+1 to k do )
sum:=sum+(s[i]-s[j])*(s[i]-s[j]);

end.

例10、 2002年初赛题
有n种基本物质(n≤10),分别记为P1,P2,……,Pn,用n种基本物质构造物品, 这些物品使用在k个不同地区(k≤20),每个地区对物品提出自己的要求,这些要 求用一个n位的数表示:α1α2……αn,其中: αi =1表示所需物质中必须有第i种基本物质 =-1表示所需物质中必须不能有第i种基本物质 =0无所谓 问题求解:

当k个不同地区要求给出之后,给出一种方案,指出哪些物质被使用,哪些 物质不被使用。
程序说明:

数组b[1],b[2],...,b[nJ表示某种物品
a[1..k,1..n]记录k个地区对物品的要求,其中: a[i,j]=1表示第i个地区对第j种物品是需要的 a[i,j]=0表示第i个地区对第j种物品是无所谓的 a[i,j]=-1表示第i个地区对第j种物品是不需要的

var
i, j ,k, n :integer; p:boolean;

while( p and (b[0]=0) )do

begin
j:=n; while b[j]=1 do j:=j-1;

产生一种 新的方案

b :array [0..20] of 0..1;
a :array[1..20,1..10]d integer; begin

( b[j]:=1 ); for i:=j+1 to n do b[i]:=0; p:=false ); ( for i:=1 to k do

检验当前方案 有没有冲突 for i:=1 to k do
readln(n,k);
begin

for j :=1 to n do (a[i,j]=-1)and(b[j]=1) if(a[i,j]=1)and(b[j]=0)or( )
then p:=true;

for j:=1 to n do read(a[i,j]);
readln;

end; if( p )then writeln('找不到!‘)
else for i:=1 to n do if (b[i]=1) then writeln('物质',i,’需要') else writeln('物质',i,'不需要'); end.

end;
for i:=0 to n do b[i]:=0; p:=true;

例11、选数
已知n(1<=n<=20)个整数x1,x2,…,xn(1<=xi<=5000000),以及一 个整数k(k<n)。从n个整数中任选k个整数相加,可分别得到一系列的 和。 例如当n=4,k=3,4个整数分别为3,7,12,19时,可得到的全部组 合及它们的和为3+7+12=22,3+7+19=29,7+12+19=38,3+12+19=34。 现在,要求你计算出和为素数的组合共有多少种。如上例中,只有一 种组合的和为素数:3+7+19=29。 输入: n,k x1,x2,…,xn 输出: 一个整数(满足条件的组合个数) 样例 输入: 4 3 3 7 12 19 输出: 1

本题可分解成以下两部分: ①从n个数中任取k个数的组合 因为n<=20,所以可以用穷举来实现。a[1], a[2] ,…, a[k]表示每种组合中 各数在原数列中的位置,a[0]是循环开关,初始时a[0]=0,当a[0]=1时穷举 结束。 当选用前面的输入样例,n=4,k=3时,a[0]~a[3]的变化如下表所示:

a[0] 0 0 0 0 1

a[1] 1 1 1 2 2

a[2] 2 2 3 3 3

a[3] 3 4 4 4 4

生成的组合 3 3 3 7 7 7 12 19

12 19 12 19

循环结束

结合上表,我们可以总结出a[j]的变化范围是j~j+n-k,且a[j-1]< a[j] 。

②判断一个整数是否为素数 判断一个整数s是否为素数最简单的方法就是试除法。即 y=trunc(sqrt(s)),然后用2,3,…,y去试除,当有一个除尽时,即非素数, 否则为素数。由于在此题中1<=xi<=5000000,n<=20,所以有些数据在运行 时可能会超时。 如何加快速度?可以从判断素数这个地方着手。 我们可以预先将2…10000之间的素数(共1229个)全部计算出来,存储 到数组中。然后看其中是否存在一个素数a(<=sqrt(s))是s的约数,如果不存 在,该数就为素数。此法可大大加快速度。

程序如下:
var n,k,j,i:integer;

sum,total:longint;
x:array[1 .. 20] of longint;{存储原始数列} a:array[0 .. 20] of integer;{记录各组合中各数在原数列中的位置 }

p:array[1 .. 1229] of integer;{存储10000以内的素数,共1229个}

procedure get_prime; var i,j,s:integer; f:array[1..10000] of 0..1; begin s:=0; f[1]:=0; for i:= 2 to 10000 do f[i]:=1; for i:= 2 to 100 do if f[i]=1 then begin s:=s+1; p[s]:=i; j:=2*i; while j<=10000 do begin f[j]:=0; j:=j+i; end; end;

function fit(sum:longint):boolean; {判断k个整数之和是否为素数} var max,m:integer; begin max:=trunc(sqrt(sum))+1; m:=1;
while(sum mod p[m]<>0)and(p[m]<max) do

m:=m+1; if p[m]>=max then fit:=true else fit:=false; end;

function tj(n,k:integer):longint; var total:longint; 产生第一种组合, begin a[0]=0是循环开关 total:=0; for i:=0 to k do a[i]:=i; while( a[0]=0 )do begin sum:=0; for i:=1 to k do sum:=( sum+x[a[i]] ); if( fit(sum) )then total:=total+1; 产生 j:=k; 一种 while( a[j]=n-k+j )do j:=j-1; 新的 a[j]:=a[j]+1; 组合 for i:=j+1 to k do( a[i]:=a[i-1]+1 ); end; tj:=total; end; begin get_prime; {用筛选法建立10000以内的素数集合} readln(n,k); for i:=1 to n do read(x[i]); total:=tj(n,k); writeln(total); end.

求当前组合的 k个整数之和

例12、开心的金明
【问题描述】 金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间他自 己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间 需要购买哪些物品,怎么布置,你说了算,只要不超过N元钱就行”。今 天一早金明就开始做预算,但是他想买的东西太多了,肯定会超过妈妈限 定的N元。于是,他把每件物品规定了一个重要度,分为5等:用整数1~5 表示,第5等最重要。他还从因特网上查到了每件物品的价格(都是整数 元)。他希望在不超过N元(可以等于N元)的前提下,使每件物品的价 格与重要度的乘积的总和最大。 设第j件物品的价格为v[j],重要度为w[j],共选中了k件物品,编 号依次为j1,j2,……,jk,则所求的总和为: v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk] 请你帮助金明设计一个满足要求的购物单。

【输入文件】 输入文件happy.in 的第1行,为两个正整数,用一个空格隔开: N m(其中N(<30000)表示总钱数,m(<25)为希望购买物品的个数。) 从第2行到第m+1行,第j行给出了编号为j-1的物品的基本数据,每行有 2个非负整数v p(其中v表示该物品的价格(v<=10000),p表示该物品的重 要度(1~5)) 【输出文件】 输出文件happy.out只有一个正整数,为不超过总钱数的物品的价格与 重要度乘积的总和的最大值(<100000000)。 【输入样例】 1000 5 800 2 400 5 300 5 400 3 200 2 【输出样例】 3900

可以通过8个测试点
var v,p:array[1..25] of integer; b:array[0..25] of 0..1; n,m,i,j,max,s,yu,l:longint; begin readln(n,m); for i:=1 to m do readln(v[i],p[i]); for i:=0 to m do b[i]:=0; while b[0]=0 do begin j:=m; while b[j]=1 do j:=j-1; b[j]:=1;
for l:= j+1 to m do b[l]:=0;

s:=0; yu:=0; for i:=1 to m do if (b[i]=1) then begin yu:=yu+v[i]; s:=s+v[i]*p[i]; end; if (yu<=n)and (s>max) then max:=s; end; writeln(max); end.


相关文章:
NOIP复赛题集
NOIP复赛模拟题 2页 2财富值 noip复赛模拟题 7页 2财富值 noip讲义3-复赛入门...本算法采用穷举法结合二进制数 据的排列来穷举所有价值组合 主要思想: 根据物品...
历届NOIP搜索算法全集
NOIP搜索算法 58页 5财富值 NOIP实用算法搜索 6页 免费 七中算法教程 信息学...采用穷举法,用一个 B 数组来表示取数的标记,当 B=0 时表示第 i 件物品不...
更多相关标签: