最佳答案

7.1 貪策略定義 7.2 貪策略特點(diǎn) 7.3 典型例題與習(xí)題 眾計(jì)算機(jī)解題策略貪策略算接近思維種解題策略基于貪策略各級(jí)各類信息競(jìng)賽、尤其NPC類問(wèn)題求解發(fā)揮著越越重要作用 7.1 貪策略定義 貪策略:指問(wèn)題初始狀態(tài)發(fā)通若干貪選擇優(yōu)值(或較優(yōu)解)種解題 其實(shí)貪策略詞我便看貪策略總做前看優(yōu)選擇說(shuō)貪策略并整體加考慮所做選擇某種意義局部?jī)?yōu)解許問(wèn)題自身特性決定該題運(yùn)用貪策略優(yōu)解或較優(yōu)解 例1:n行m列整數(shù)矩陣要求每行選數(shù)使選n數(shù) 本題用貪策略:選n每選相應(yīng)行值即 例2:N×M格陣每格賦予數(shù)(即權(quán))規(guī)定每移能向或向右現(xiàn)試找條路徑使其左角至右角所經(jīng)權(quán) 本題用貪策略能優(yōu)解我2×4矩陣?yán)?3 4 6 1 2 10 若按貪策略求解所路徑:1,3,4,6; 若按態(tài)規(guī)劃求解所路徑:1,2,10,6 例3:設(shè)定n臺(tái)處理機(jī)p1p2......pn,m作業(yè)j1,j2,...jm,處理機(jī)并行工作,作業(yè)未完能斷作業(yè)ji處理機(jī)處理間ti,求解佳案,使完m項(xiàng)工作間短? 本題能用貪算求解:理由若n=3,m=6 各作業(yè)間別11 7 5 5 4 7 用貪策略解(每作業(yè)加先空閑機(jī)器)time=15,用搜索策略優(yōu)間應(yīng)14,貪策略給我提供線索每臺(tái)處理間超15,給搜索提供便 總: 1. 能保證求解佳; 2. 能用求某些或解問(wèn)題; 3. 能確定某些問(wèn)題行解范圍特別給搜索算提供依據(jù) 7. 2 貪策略特點(diǎn) 貪算特點(diǎn)呢我認(rèn)適用于貪算解決問(wèn)題應(yīng)具2特點(diǎn): 1、貪選擇性質(zhì): 所謂貪選擇性質(zhì)指應(yīng)用同規(guī)則f原問(wèn)題變相似、規(guī)模更問(wèn)題、每步都前看似佳選擇種選擇依賴于已做選擇依賴于未做選擇全局看運(yùn)用貪策略解決問(wèn)題程序運(yùn)行程溯程關(guān)于貪選擇性質(zhì)讀者文給貪策略狀態(tài)空間圖深刻體 2、局部?jī)?yōu)解: 我通特點(diǎn)2向家介紹貪策略數(shù)描述由于運(yùn)用貪策略解題每都取優(yōu)解能夠保證局部?jī)?yōu)解定貪算家所熟悉態(tài)規(guī)劃算滿足局部?jī)?yōu)解貪策略比態(tài)規(guī)劃間效率更高站用內(nèi)存更少編寫(xiě)程序更簡(jiǎn)單 7.3 典型例題與習(xí)題 例4:背包問(wèn)題: 背包背包容量M=1507物品物品割任意 要求盡能讓裝入背包物品總價(jià)值能超總?cè)萘?物品 A B C D E F G 重量 35 30 60 50 40 10 25 價(jià)值 10 40 30 50 35 40 30 析: 目標(biāo)函數(shù): ∑pi 約束條件裝入物品總重量超背包容量:∑wi<=M( M=150) (1)根據(jù)貪策略每挑選價(jià)值物品裝入背包結(jié)否優(yōu) (2)每挑選所占空間物品裝入否能優(yōu)解 (3)每選取單位容量?jī)r(jià)值物品解本題策略 程序: 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,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]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. 例5:旅行家預(yù)算問(wèn)題: 旅行家想駕駛汽車少費(fèi)用城市另城市給定兩城市間距離d1汽車油箱容量c每升汽油能行駛距離d2發(fā)每升汽油價(jià)格p沿途加油站數(shù)n(0)油站i離發(fā)點(diǎn)距離di每升汽油價(jià)格pi 計(jì)算結(jié)四舍五入保留數(shù)點(diǎn)兩位若達(dá)目輸No answer" 若輸入: d1=275.6 c=11.9 d2=27.4 p=8 n=2 d[1]=102 p[1]=2.9 d[2]=220 p[2]=2.2 output 26.95 本問(wèn)題貪策略:找較便宜油站根據(jù)距離確定加滿、加、加剛該站 程序: 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. 例6:n部件,每部件必須經(jīng)先AB兩道工序 知部件iA,B 機(jī)器間別aibi何安排加工順序總加工間短 輸入: 5 部件 1 2 3 4 5 ai 3 5 8 7 10 bi 6 2 1 4 9 輸: 34 1 5 4 2 3 本問(wèn)題貪策略A機(jī)器加工短應(yīng)優(yōu)先B機(jī)器加工短應(yīng)靠 程序: 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].ai 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

回答者：mxozeu2016-10-12 00:00