最佳答案

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