算法設(shè)計(jì)與分析 課件 5.4.2-動(dòng)態(tài)規(guī)劃-0-1背包問(wèn)題-動(dòng)態(tài)規(guī)劃求解

信息工程大學(xué)算法設(shè)計(jì)與分析動(dòng)態(tài)規(guī)劃—0-1背包問(wèn)題之動(dòng)態(tài)規(guī)劃求解國(guó)家級(jí)實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版動(dòng)態(tài)規(guī)劃解題步驟：找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值。以自底向上的方式計(jì)算出最優(yōu)值。根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。定義：f(i,j)表示背包容量為j、可選物品編號(hào)為i,i+1,…,n時(shí)0-1背包問(wèn)題的最優(yōu)值。1.找出最優(yōu)解性質(zhì)，刻畫結(jié)構(gòu)特征f(i,j)表示背包容量為j、可選物品編號(hào)為i,i+1,…,n時(shí)0-1背包問(wèn)題的最優(yōu)值。2.遞歸地定義最優(yōu)值nn-1i+1i……1

定義二維數(shù)組f[n+1][c+1]首列初始化000ed0ab000n1j-wici1

f(i,j)=max{vi

+f(i+1,j-wi),f(i+1,j)}i+1j3.以自底向上的方式計(jì)算最優(yōu)值自下而上、自左而右重疊子問(wèn)題實(shí)例分析：初始化物品編號(hào)重量?jī)r(jià)值1212211033204215背包容量c=5，物品個(gè)數(shù)n=400000123452341ijc=5，n=4f數(shù)組實(shí)例分析：計(jì)算f(4,j)物品重量?jī)r(jià)值1212211033204215c=5，n=4000000123452341ijf數(shù)組

實(shí)例分析：計(jì)算f(4,j)物品重量?jī)r(jià)值1212211033204215c=5，n=400000150123452341ijf數(shù)組

實(shí)例分析：計(jì)算f(4,j)物品重量?jī)r(jià)值1212211033204215c=5，n=400000151515150123452341ijf數(shù)組

實(shí)例分析：計(jì)算f(3,j)物品重量?jī)r(jià)值1212211033204215015202035c=5，n=400000151515150123452341ijf數(shù)組

實(shí)例分析：計(jì)算f(2,j)物品重量?jī)r(jià)值1212211033204215c=5，n=40010001520203500151515150123452341ijf數(shù)組

實(shí)例分析：計(jì)算f(2,j)物品重量?jī)r(jià)值1212211033204215c=5，n=4001015253035001520203500151515150123452341ijf數(shù)組

實(shí)例分析：計(jì)算f(1,j)物品重量?jī)r(jià)值1212211033204215c=5，n=40101525303701015253035001520203500151515150123452341ijf數(shù)組

打表法！算法描述Knapsack(n,c)1for

j

←0to

wn-1do

f[n,j]←0;2for

j

←

wn

to

c

do

f[n,j]←

vn;3for

i

←

n-1

to

1

do4for

j

←

0

to

c

do5if

wi>j

then6f[i,j]←

f[i+1,j];7else8f[i,j]←max{f[i+1,j],f[i+1,j-wi]+vi}時(shí)間復(fù)雜度T(n)=O(cn)方法：從問(wèn)題最優(yōu)值開始倒推0000000:n1w-wici1i+1w五4.根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解

f(i,j)=max{vi

+f(i+1,j-wi),f(i+1,j)}01015253037010