4.1 原始遞迴法
4.2 改進遞迴法
4.3 習題
4.1 原始遞迴法
先看完全揹包問題
乙個旅行者有乙個最多能用m公斤的揹包，現在有n種物品，每件的重量分別是w1，w2，...,wn,
每件的價值分別為c1,c2,...,cn.若的每種物品的件數足夠多.
求旅行者能獲得的最大總價值。
本問題的數學模型如下：
設 f(x)表示重量不超過x公斤的最大價值，則 f(x）=max 當x>=w[i] 1<=i<=n可使用遞迴法解決問題程式如下:
program knapsack04;
const maxm=200;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
function f(x:integer):integer;
var i,t,m:integer;
begin
if x=0 then f:=0 elsebegin
t:=-1;
for i:=1 to n do
begin
if x>=w[i] then m:=f(x-i)+c[i];
if m>t then t:=m;
end;
f:=t;
end;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
writeln(f(m));
end.
說明:當m不大時,程式設計很簡單,但當m較大時,容易超時.
4.2 改進的遞迴法
改進的的遞迴法的思想還是以空間換時間,這只要將遞迴函式計算過程中的各個子函式的值儲存起來,開闢乙個
一維陣列即可
程式如下:
program knapsack04;
const maxm=2000;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
p:array[0..maxm] of integer;
function f(x:integer):integer;
var i,t,m:integer;
begin
if p[x]<>-1 then f:=p[x]else
begin
if x=0 then p[x]:=0 elsebegin
t:=-1;
for i:=1 to n do
begin
if x>=w[i] then m:=f(i-w[i])+c[i];
if m>t then t:=m;
end;
p[x]:=t;
end;
f:=p[x];
end;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
fillchar(p,sizeof(p),-1);
writeln(f(m));
end.
4.3習題
用改進的遞迴法解資源分配問題:
n個資源分配到m個專案上，i專案分配j個資源可獲益a[i,j],求最大總效益。
動態規劃DP的使用條件
任何思想方法都有一定的侷限性，超出了特定條件，它就失去了作用。同樣，動態規劃也並不是萬能的。適用動態規劃的問題必須滿足最優化原理和無後效性。1.最優化原理 最優子結構性質 最優化原理可這樣闡述 乙個最優化策略具有這樣的性質，不論過去狀態和決策如何，對前面的決策所形成的狀態而言，餘下的諸決策必須構成最...
函式的表示法教學設計
1 掌握函式的三種表示方法 圖象法 列表法 解析法 會根據不同的需要選擇恰當的方法表示函式 通過具體的例項，在不同的表示法的選擇 轉化中，逐步學會用恰當的方法表示乙個函式，逐步養成用不同方法表示乙個函式的習慣，尤其是增強數與形結合的意識 2 了解簡單的分段函式，並能簡單的應用 通過具體例項 如計程車...
《函式的表示法》導學案
高一數學編號 sx 11 01 008 撰稿 黃先政審核 張春娥時間 2011 9 15 姓名班級 組別 組名 學習目標 1.了解函式的一些表示法，會根據不同情境選擇合適的方法表示函式，樹立應用數形結合的思想 2.通過具體事例。了解簡單的分段函式，並能簡單應用 3.會用描點法畫一些簡單函式圖象，培養...