求贪心算法题（Pascal）
\u8d2a\u5fc3\u7b97\u6cd5\u7684\u4f8b\u9898\u5206\u6790program beibao;
const
m=150;
n=7;
var
xu:integer;
i,j:integer;
goods:array[1..n,0..2] of integer;
ok:array[1..n,1..2] of real;
procedure init;
var
i:integer;
begin
xu:=m;
for i:=1 to n do
begin
write('Enter the price and weight of the ',i,'th goods:');
goods[i,0]:=i;
read(goods[i,1],goods[i,2]);
readln;
ok[i,1]:=0; ok[i,2]:=0;
end;
end;
procedure make;
var
bi:array[1..n] of real;
i,j:integer;
temp1,temp2,temp0:integer;
begin
for i:=1 to n do
bi[i]:=goods[i,1]/goods[i,2];
for i:=1 to n-1 do
for j:=i+1 to n do
begin
if bi[i]<bi[j] then begin
temp0:=goods[i,0]; temp1:=goods[i,1]; temp2:=goods[i,2];
goods[i,0]:=goods[j,0]; goods[i,1]:=goods[j,1]; goods[i,2]:=goods[j,2];
goods[j,0]:=temp0; goods[j,1]:=temp1; goods[j,2]:=temp2;
end;
end;
end;
begin
init;
make;
for i:=1 to 7 do
begin
if goods[i,2]>xu then break;
ok[i,1]:=goods[i,0]; ok[i,2]:=1;
xu:=xu-goods[i,2];
end;
j:=i;
if i<=n then
begin
ok[i,1]:=goods[i,0];
ok[i,2]:=xu/goods[i,2];
end;
for i:=1 to j do
writeln(ok[i,1]:1:0,':',ok[i,2]*goods[i,2]:2:1);
end.
旅行家问题
program jiayou;
const maxn=10001;
zero=1e-16;
type
jd=record
value,way,over:real;
end;
var oil:array[1..maxn] of ^jd;
n:integer;
d1,c,d2,cost,maxway:real;
function init:boolean;
var i:integer;
begin
new(oil[1]);
oil[1]^.way:=0;
read(d1,c,d2,oil[1]^.value,n);
maxway:=d2*c;
for i:=2 to n+1 do
begin
new(oil[i]);
readln(oil[i]^.way,oil[i]^.value);
oil[i]^.over:=0;
end;
inc(n,2);
new(oil[n]);
oil[n]^.way:=d1;
oil[n]^.value:=0;
oil[n]^.over:=0;
for i:=2 to n do
if oil[i]^.way-oil[i-1]^.way>maxway then
begin
init:=false;
exit
end;
init:=true;
end;
procedure buy(i:integer;miles:real);
begin
cost:=cost+miles/d2*oil[i]^.value;
end;
procedure solve;
var i,j:integer;
s:real;
begin
i:=1;j:=i+1;
repeat
s:=0.0;
while( s<=maxway+zero) and (j<=n-1) and (oil[i]^.value<=oil[j]^.value) do
begin
inc(j);
s:=s+oil[j]^.way-oil[j-1]^.way
end;
if s<=maxway+zero then
if (oil[i]^.over+zero>=oil[j]^.way-oil[i]^.way) then
oil[j]^.over:=oil[i]^.over-(oil[j]^.way-oil[i]^.way) else
begin
buy(i,oil[j]^.way-oil[i]^.way-oil[i]^.over);
oil[j]^.over:=0.0;
end
else begin
buy(i,maxway-oil[i]^.over);
j:=i+1;
oil[j]^.over:=maxway-(oil[j]^.way-oil[i]^.way);
end;
i:=j;
until i=n;
end;
begin
cost:=0;
if init then begin
solve;
writeln(cost:0:2);
end else writeln('No answer');
end.
n个部件,每个部件必须经过先A后B两道工序
program workorder;
const maxn=100;
type jd=record
a,b,m,o:integer;
end;
var n,min,i:integer;
c:array[1..maxn] of jd;
order:array[1..maxn] of integer;
procedure init;
var i:integer;
begin
readln(n);
for i:=1 to n do
read(c[i].a);
readln;
for i:=1 to n do
read(c[i].b);
readln;
for i:=1 to n do
begin
if c[i].a<c[i].b then c[i].m:=c[i].a else c[i].m:=c[i].b;
c[i].o:=i;
end;
end;
procedure sort;
var i,j,k,t:integer;
temp:jd;
begin
for i:=1 to n-1 do
begin
k:=i;t:=c[i].m;
for j:=i+1 to n do
if c[j].m<t then begin t:=c[j].m;k:=j end ;
if k<>i then begin temp:=c[i];c[i]:=c[k];c[k]:=temp end
end;
end;
procedure playorder;
var i,s,t:integer;
begin
fillchar(order,sizeof(order),0);
s:=1;
t:=n;
for i:=1 to n do
if c[i].m=c[i].a then begin order[s]:=i;s:=s+1 end
else begin order[t]:=i;t:=t-1;end;
end;
procedure calc_t;
var i,t1,t2:integer;
begin
t1:=0;t2:=0;
for i:=1 to n do
begin
t1:=t1+c[order[i]].a;
if t2<t1 then t2:=t1;
t2:=t2+c[order[i]].b;
end;
min:=t2;
end;
begin
init;
sort;
playorder;
calc_t;
writeln(min);
for i:=1 to n do
write(c[order[i]].o,' ');
writeln;
end.
没时间写了凑合着看看，履行承诺啊追加分数
《编程之美》里面有一道买书问题的贪心算法。
题目是这样的：
在节假日的时候，书店一般都会做促销活动。由于《哈利波特》系列相当畅销，店长决定通过促销活动来回馈读者。上柜的《哈利波特》平装本系列中，一共有五卷。假设每一卷单独销售均需8欧元 。如果读者一次购买不同的两卷，就可以扣除5%的费用，三卷则更多。假设具体折扣的情况如下：
本数 折扣
2 5%
3 10%
4 20%
5 25%
在一份订单中，根据购买的卷数及本数，就会出现可以应用不同折扣规则的情况。但是，一本书只会应用一个折扣规则。比如，读者一共买了两本卷一，一本卷二。那么，可以享受到5%的折扣。另外一本卷一则不能享受折扣。如果有多种折扣，希望计算出的总额尽可能的低。
要求根据以上需求，设计出算法，能够计算出读者所购买一批书的最低价格。
绛旓細O(VN)鐨绠楁硶 澶氶噸鑳屽寘闂鍚屾牱鏈塐(VN)鐨勭畻娉曘傝繖涓畻娉曞熀浜庡熀鏈畻娉曠殑鐘舵佽浆绉绘柟绋,浣嗗簲鐢ㄥ崟璋冮槦鍒楃殑鏂规硶浣挎瘡涓姸鎬佺殑鍊煎彲浠ヤ互鍧囨憡O(1)鐨勬椂闂存眰瑙ｃ傜敱浜庣敤鍗曡皟闃熷垪浼樺寲鐨凞P宸茶秴鍑轰簡NOIP鐨勮寖鍥,鏁呮湰鏂囦笉鍐嶅睍寮璁茶В銆傛垜鏈鍒濅簡瑙ｅ埌杩欎釜鏂规硶鏄湪妤煎ぉ鎴愮殑鈥滅敺浜哄叓棰樷濆够鐏墖涓娿 灏忕粨杩欓噷鎴戜滑鐪嬪埌浜嗗皢涓涓畻娉曠殑澶嶆潅...
绛旓細鑻>X[I], 鍒欓绀虹潃锛屾苯杞﹀紑鍒版补绔橩锛屼粛鐒舵湁娌瑰墿浣欍傚亣璁惧墿浣橶鍔犱粦姹芥补锛屽垯椤昏垂鐢╒alue[I]*W锛屽鏋淲鍔犱粦姹芥补鍦ㄦ补绔橩鍔狅紝鍒欓』璐圭敤Value[K]*W锛屾樉鐒禫alue[K]*W<Value[I]*W銆傗憽 鑻alue[I]<Value[k]锛屽垯鎸璐績瑙勫垯锛岄』鍔犳补涓 T=C-Over[I] 锛堝嵆鍔犳弧娌癸級銆傝嫢T<X[I]锛屽垯琛ㄧず鍦...
绛旓細杩欓涔熻鏄璐績绠楁硶鐨勪竴涓畝鍗曞簲鐢 銆備竴寮濮嬫垜鏄繖涔堟兂鐨勶細浣嗘槸椹笂灏辨帹缈讳簡杩欑绠鍗曠殑绠楁硶锛氬鏋滅粰绗竴涓汉7棰楃硸锛岀浜屼釜浜3棰楋紝閭ｄ箞鐢熸皵鎸囨暟鏄細灏界涓婅堪鐪嬩技瀵逛簬瑙ｉ娌″お澶у府鍔╋紝浣嗘槸浜嗚В涓涓濊冭繃绋嬫垜瑙夊緱涔熸槸鏈夊繀瑕佺殑銆備簨瀹炰笂锛屽畠鍚彂浜嗘垜鎵惧埌涓嬮潰杩欎釜搴旇姝ｇ‘鐨勭畻娉曘傗斺斺36锛屾瘮涓寮濮嬬殑55灏...
绛旓細program beibao;const m=150;n=7;var xu:integer;i,j:integer;goods:array[1..n,0..2] of integer;ok:array[1..n,1..2] of real;procedure init;var i:integer;begin xu:=m;for i:=1 to n do begin write('Enter the price and weight of the ',i,'th goods:');goods[i,...
绛旓細杩欐槸鍏稿瀷鐨璐績绠楁硶锛涘嚱鏁癿ax渚挎槸姹傛渶澶у硷紱杩欏彞璇濆氨鏄妸鎬т环姣旀渶浼橈紙涔熷氨鏄渶澶х殑锛夊敖閲忓閫
绛旓細璐績绠楁硶瀹炶川涓婂氨鏄瘡涓姝ラ兘鍙栨渶浼樿В銆傛瘮濡傝儗鍖呴棶棰橈紙涓嶆槸0/1鍜屽畬鍏紝鏈鍘熷鐨勯偅绉嶏級鍙互鐢ㄨ椽蹇冨揩閫熻В鍐炽傚緢鏄剧劧锛屽畠鏈夌洰鍏夌煭娴呯殑闂锛屽緢澶棰樼洰杩樻槸瑕佺敤鍔ㄦ佽鍒掔殑 璐績绠楁硶 1锛庢蹇 璐績绠楁硶鏄粠闂鐨勬煇涓涓垵濮嬭В鍑哄彂閫愭閫艰繎缁欏畾鐨勭洰鏍囷紝浠 灏藉彲鑳藉揩鍦版眰寰楁洿濂界殑瑙ｃ傚綋杈惧埌鏌愮畻娉曚腑鐨勬煇涓姝ヤ笉...
绛旓細璐績绠楁硶杩樻槸寰堝父瑙佺殑绠楁硶涔嬩竴锛岃繖鏄敱浜庡畠绠鍗曟槗琛岋紝鏋勯犺椽蹇冪瓥鐣ヤ笉鏄緢鍥伴毦銆傚彲鎯滅殑鏄紝瀹冮渶瑕佽瘉鏄庡悗鎵嶈兘鐪熸杩愮敤鍒棰樼洰鐨勭畻娉曚腑銆備竴鑸潵璇达紝璐績绠楁硶鐨勮瘉鏄庡洿缁曠潃锛氭暣涓棶棰樼殑鏈浼樿В涓瀹氱敱鍦ㄨ椽蹇冪瓥鐣ヤ腑瀛樺湪鐨勫瓙闂鐨勬渶浼樿В寰楁潵鐨勩傚浜渚嬮涓殑3绉嶈椽蹇冪瓥鐣ワ紝閮芥槸鏃犳硶鎴愮珛锛堟棤娉曡璇佹槑锛夌殑锛岃В閲婂涓...
绛旓細begin readln(b);a:=trunc(b*100);//杞崲鎴愪互鍒嗕负鍗曚綅鐨勯挶鏁帮紝渚夸簬璁＄畻 for i:=1 to 10 do//浠10鍏冨紑濮嬫灇涓 begin if a>rmb[i] then begin//涓鏃﹁兘澶熲滄崲寮鈥漣nc(ans[i],a div rmb[i]);//璁颁笅鏉ョ敤浜嗗灏戝紶 inc(tot,a div rmb[i]);//鍚屼笂 dec(a,a div rmb[i]*rmb[i]...
绛旓細杩欓亾棰樺簲璇ユ槸浣跨敤璐績绠楁硶鍚с傘傚厛浠ヨ捣濮嬩綅缃帓搴忕嚎娈碉紝鐒跺悗 姣斿鐜板湪宸茬粡瑕嗙洊浜唜鐨勫尯闂淬傚鎵句互1~x-1涓哄紑濮嬬殑鍖洪棿閲岃兘鍚戜笅鎵╁睍鏈澶氱殑绾挎銆傚疄闄呬笂涓嶉渶瑕佹瘡娆￠兘瀵绘壘1~x-1銆備腑闂寸敤杩囦竴涓嚎娈碉紝鍓嶉潰鐨勯兘鏄棤鐢ㄧ殑銆傚洜姝ゅ彧闇瑕佷竴涓彉閲忚褰曟煡鍒板摢閲屽氨琛屼簡 O锛坣锛夌畻娉 澶ф鏄繖鏍凤紙浼唬鐮侊級s绾挎寮濮...
绛旓細璐績绠楁硶灏辫浜.鏈鍏堢剨鎺ョ殑涓瀹氱疮绉簡鏈澶氭,鎵浠ユ瘡娆￠兘閫夊嚭褰撳墠鏈鐭殑涓ゆ牴鐒婃帴灏辫浜.鍏蜂綋瀹炵幇鍙互浣跨敤鍫.浣犲皾璇曞幓鍐欏惂..杩欏緢绠鍗曚簡.--- 閲嶆柊鐪嬩簡涓娆棰樼洰渚濈劧瑙夊緱鏄椽蹇,濡傛灉鍙兘鎶婃垜鐨勪唬鐮佷篃浜や笂鍘昏瘯璇曞惂.闅忎究鎵句簡涓涓爢鐨勪唬鐮佹敼鍐欑殑鎵浠ユ湁鐐归暱.var i,n,top,x,a,b,ans:longint;heap:...
