C語言動(dòng)態(tài)規(guī)劃課件

第五章動(dòng)態(tài)規(guī)劃第五章動(dòng)態(tài)規(guī)劃11海盜分金問題5名海盜搶得了窖藏的100塊金子，并打算瓜分這些戰(zhàn)利品。這是一些講民主的海盜（當(dāng)然是他們自己特有的民主），他們的習(xí)慣是按下面的方式進(jìn)行分配：最厲害的一名海盜提出分配方案，然后所有的海盜（包括提出方案者本人）就此方案進(jìn)行表決。如果50%或更多的海盜贊同此方案，此方案就獲得通過并據(jù)此分配戰(zhàn)利品。否則提出方案的海盜將被扔到海里，然后下一名最厲害的海盜又重復(fù)上述過程。1海盜分金問題5名海盜搶得了窖藏的100塊金子，并打算瓜分2所有的海盜都樂于看到他們的一位同伙被扔進(jìn)海里，不過，如果讓他們選擇的話，他們還是寧可得一筆現(xiàn)金。他們當(dāng)然也不愿意自己被扔到海里。所有的海盜都是聰明絕頂?shù)模抑榔渌暮１I也是聰明絕頂?shù)?。此外，沒有兩名海盜是同等厲害的——這些海盜按照完全由上到下的等級排好了座次，并且每個(gè)人都清楚自己和其他所有人的等級。這些金塊不能再分，也不允許幾名海盜共有金塊，因?yàn)槿魏魏１I都不相信他的同伙會(huì)遵守關(guān)于共享金塊的安排。這是一伙每人都只為自己打算的海盜。所有的海盜都樂于看到他們的一位同伙被扔進(jìn)海里，不過，如果讓他3最兇的一名海盜應(yīng)當(dāng)提出什么樣的分配方案才能使他獲得最多的金子呢？我們按照這些海盜的威望值來給他們編號(hào)。最怯懦的海盜為1，最厲害的海盜編號(hào)為5。編號(hào)為5的海盜會(huì)提出什么分配方案呢？最兇的一名海盜應(yīng)當(dāng)提出什么樣的分配方案才能使他獲得最多的金子4如果從游戲的開頭出發(fā)進(jìn)行分析，那是走不了多遠(yuǎn)的。其原因在于，所有的戰(zhàn)略決策都是要確定：“如果我這樣做，那么下一個(gè)人會(huì)怎樣做？”因此在你以下海盜所做的決定對你來說是重要的，而在你之前的海盜所做的決定并不重要，因?yàn)槟惴凑龑@些決定也無能為力了。如果從游戲的開頭出發(fā)進(jìn)行分析，那是走不了多遠(yuǎn)的。5最厲害的5號(hào)海盜需要知道其他4名海盜是怎么想的.......好難猜！對4號(hào)海盜來說，如果5號(hào)海盜被扔進(jìn)海里喂鯊魚了，他只需要猜透其余3名海盜的算盤。對3號(hào)海盜而言，他只須猜透1號(hào)和2號(hào)海盜對2號(hào)海盜而言，他只須猜透1號(hào)海盜那我們就倒過來，由易到難最厲害的5號(hào)海盜需要知道其他4名海盜是怎么想的.......6我們的出發(fā)點(diǎn)應(yīng)當(dāng)是游戲進(jìn)行到只剩兩名海盜——即1號(hào)和2號(hào)——的時(shí)候。這時(shí)最厲害的海盜是2號(hào)，而他的最佳分配方案是一目了然的：100塊金子全歸他一人所有，1號(hào)海盜什么也得不到。3號(hào)海盜的分配方案：3號(hào)海盜分得99塊金子，2號(hào)海盜一無所獲，1號(hào)海盜得1塊金子。1號(hào)海盜知道，如果3號(hào)的方案被否決，那么最后將只剩2個(gè)海盜，而1號(hào)將肯定一無所獲——此外，3號(hào)也明白1號(hào)了解這一形勢。因此，只要3號(hào)的分配方案給1號(hào)一點(diǎn)甜頭使他不至于空手而歸，那么不論3號(hào)提出什么樣的分配方案，1號(hào)都將投贊成票。因此3號(hào)需要分出盡可能少的一點(diǎn)金子來賄賂1號(hào)海盜我們的出發(fā)點(diǎn)應(yīng)當(dāng)是游戲進(jìn)行到只剩兩名海盜——即1號(hào)和2號(hào)——74號(hào)的分配方案應(yīng)是：99塊金子歸自己，3號(hào)一塊也得不到，2號(hào)得1塊金子，1號(hào)也是一塊也得不到。4號(hào)海盜的策略也差不多。他需要有50%的支持票，因此同3號(hào)一樣也需再找一人做同黨。他可以給同黨的最低賄賂是1塊金子，而他可以用這塊金子來收買2號(hào)海盜。因?yàn)槿绻?號(hào)被否決而3號(hào)得以通過，則2號(hào)將一文不名。4號(hào)的分配方案應(yīng)是：99塊金子歸自己，3號(hào)一塊也得不到，2號(hào)85號(hào)海盜的分配方案應(yīng)該是：98塊金子歸自己，1塊金子給3號(hào)，1塊金子給1號(hào)。5號(hào)海盜的策略稍有不同。他需要收買另兩名海盜，因此至少得用2塊金子來賄賂，才能使自己的方案得到采納。討論：為什么賄賂1號(hào)和3號(hào)而不是4號(hào)和2號(hào)？5號(hào)海盜的分配方案應(yīng)該是：98塊金子歸自己，1塊金子給3號(hào)，9總結(jié)分析所有這類策略游戲的奧妙就在于應(yīng)當(dāng)從結(jié)尾出發(fā)倒推回去。游戲結(jié)束時(shí)，你容易知道何種決策有利而何種決策不利?？偨Y(jié)10在現(xiàn)實(shí)生活中，有一類活動(dòng)的過程，由于它的特殊性，可將過程分成若干個(gè)互相聯(lián)系的階段，在它的每一階段都需要作出決策，從而使整個(gè)過程達(dá)到最好的活動(dòng)效果。這種把一個(gè)問題看作是一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為多階段決策過程，這種問題稱為多階段決策問題。

多階段決策問題在現(xiàn)實(shí)生活中，有一類活動(dòng)的過程，由于它的特殊性，可將過程分成117E52D1D23738C1C2C3B1B2

A755586757下圖表示城市之間的交通路網(wǎng)，線段上的數(shù)字表示費(fèi)用，單向通行由A->E。試用動(dòng)態(tài)規(guī)劃的最優(yōu)化原理求出A->E的最省費(fèi)用。2最短距離問題7E52D1378C1C2B1B2A755675712如圖從A到E共分為4個(gè)階段，即第一階段從A到B，第二階段從B到C，第三階段從C到D，第四階段從D到E。除起點(diǎn)A和終點(diǎn)E外，其它各點(diǎn)既是上一階段的終點(diǎn)又是下一階段的起點(diǎn)。例如從A到B的第一階段中，A為起點(diǎn)，終點(diǎn)有B1，B2兩個(gè)，因而這時(shí)走的路線有兩個(gè)選擇，一是走到B1，一是走到B2。若選擇B2的決策，B2就是第一階段在我們決策之下的結(jié)果，它既是第一階段路線的終點(diǎn)，又是第二階段路線的始點(diǎn)。在第二階段，再從B2點(diǎn)出發(fā)，對于B2點(diǎn)就有一個(gè)可供選擇的終點(diǎn)集合(C1，C2，C3)；若選擇由B2走至C2為第二階段的決策，則C2就是第二階段的終點(diǎn)，同時(shí)又是第三階段的始點(diǎn)。同理遞推下去，可看到各個(gè)階段的決策不同，線路就不同。如圖從A到E共分為4個(gè)階段，即第一階段從A到B，第二13很明顯，當(dāng)某階段的起點(diǎn)給定時(shí)，它直接影響著后面各階段的行進(jìn)路線和整個(gè)路線的長短。故此問題的要求是：在各個(gè)階段選取一個(gè)恰當(dāng)?shù)臎Q策，使由這些決策組成的一個(gè)決策序列所決定的一條路線，其總路程最短。如何解決這個(gè)問題呢？

要求在各階段選取一個(gè)恰當(dāng)?shù)臎Q策很明顯，當(dāng)某階段的起點(diǎn)給定時(shí)，它直接影響著后面各階14用枚舉法

把所有由A->E可能的每一條路線的距離算出來，然后互相比較，找出最短者，相應(yīng)地得出了最短路線。

用枚舉法

把所有由A->E可能的每一條路線的距離算出來，然后15用動(dòng)態(tài)規(guī)劃法求解

決策過程：

（1）由目標(biāo)狀態(tài)E向前推，可以分成四個(gè)階段，即四個(gè)子問題。DECEBEAE

（2）策略：每個(gè)階段到E的最省費(fèi)用為本階段的決策路徑。

用動(dòng)態(tài)規(guī)劃法求解

決策過程：

（1）由目標(biāo)狀態(tài)E向前推，可以16（3）D1，D2是第一次輸入的結(jié)點(diǎn)。他們到E都只有一種費(fèi)用：f(D1)=5f(D2)=2E52D1D2目前無法定下，哪一個(gè)點(diǎn)將在全程最優(yōu)策略的路徑上。第二階段計(jì)算中，5，2都應(yīng)分別參加計(jì)算（3）D1，D2是第一次輸入的結(jié)點(diǎn)。他們到E都只有一種費(fèi)用：17（4）C1，C2，C3是第二次輸入結(jié)點(diǎn)，他們到D1，D2各有兩種費(fèi)用。此時(shí)應(yīng)計(jì)算C1，C2，C3分別到E的最少費(fèi)用。

f(C1)=min{C1D1+f(D1)，C1D2+f(D2)}。計(jì)算結(jié)果是f(C1)=C1D1+f(D1)=8（D1)同理C2的決策路徑計(jì)算結(jié)果是C2+D2+E,f(C2)=7。

同理C3的決策路徑計(jì)算結(jié)果是C3+D2+E，f(C3)=10。E8752D1D23738C1C2C35710此時(shí)也無法定下第一，二階段的城市那二個(gè)將在整體的最優(yōu)決策路徑上。

（4）C1，C2，C3是第二次輸入結(jié)點(diǎn)，他們到D1，D2各有18（5）第三次輸入結(jié)點(diǎn)為B1，B2，而決策輸出結(jié)點(diǎn)可能為C1，C2，C3。仿前計(jì)算可得Bl，B2的決策路徑為如下情況。

Bl:B1C1費(fèi)用f(B1)=5+8=13，B2:B2C1費(fèi)用f(B2)=6+8=14，75B1B25867E8752D1D23738C1C2C357101314此時(shí)也無法定下第一，二，三階段的城市那三個(gè)將在整體的最優(yōu)決策路徑上。（5）第三次輸入結(jié)點(diǎn)為B1，B2，而決策輸出結(jié)點(diǎn)可能為C1，19（6）第四次輸入結(jié)點(diǎn)為A，決策輸出結(jié)點(diǎn)可能為B1，B2。同理可得決策路徑為A：AB2，費(fèi)用5+14=19此時(shí)才正式確定每個(gè)子問題的結(jié)點(diǎn)中，那一個(gè)結(jié)點(diǎn)將在最優(yōu)費(fèi)用的路徑上。子問題的決策中，只對同一城市（結(jié)點(diǎn)）比較優(yōu)劣。而同一階段的城市（結(jié)點(diǎn)）的優(yōu)劣要由下一個(gè)階段去決定。75B1B25867E8752D1D23738C1C2C357101314A1975（6）第四次輸入結(jié)點(diǎn)為A，決策輸出結(jié)點(diǎn)可能為B1，B2。7520如何用計(jì)算機(jī)實(shí)現(xiàn)上述算法？用數(shù)組來存儲(chǔ)中間結(jié)果，用空間代價(jià)換取時(shí)間效率先自底向上構(gòu)造中間結(jié)果，再自頂向下作出最優(yōu)決策如何用計(jì)算機(jī)實(shí)現(xiàn)上述算法？用數(shù)組來存儲(chǔ)中間結(jié)果，用空間代價(jià)換21ABCDEf(A)f(B1)f(C1)f(D1)0f(B2)f(C2)f(D2)f(C3)ABCDE1913850147210ABCDEB2C1D1EC1D2ED2由表二和表三作出最優(yōu)決策：AB2C1D1E表一：表二：各城市到E的最短距離表三：各城市的最優(yōu)后繼（使其到E最近）ABCDEf(A)f(B1)f(C1)f(D1)0f(B2)22小結(jié)及比較

與窮舉法相比，動(dòng)態(tài)規(guī)劃的方法有兩個(gè)明顯的優(yōu)點(diǎn):

(1)大大減少了計(jì)算量

(2)豐富了計(jì)算結(jié)果

從上例的求解結(jié)果中，我們不僅得到由A點(diǎn)出發(fā)到終點(diǎn)E的最短路線及最短距離，而且還得到了從所有各中間點(diǎn)到終點(diǎn)的最短路線及最短距離，這對許多實(shí)際問題來講是很有用的。

小結(jié)及比較

與窮舉法相比，動(dòng)態(tài)規(guī)劃的方法有兩個(gè)明顯的優(yōu)點(diǎn):

23動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個(gè)子問題3.動(dòng)態(tài)規(guī)劃總體思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若24但是經(jīng)分解得到的子問題往往不是互相獨(dú)立的。不同子問題的數(shù)目常常只有多項(xiàng)式量級。在用遞歸法求解時(shí)，有些子問題被重復(fù)計(jì)算了許多次。算法總體思想nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)但是經(jīng)分解得到的子問題往往不是互相獨(dú)立的。不同子問題的數(shù)目常25如果能夠保存已解決的子問題的答案，而在需要時(shí)再找出已求得的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。算法總體思想n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)如果能夠保存已解決的子問題的答案，而在需要時(shí)再找出已求得的答26是先把問題分成多個(gè)子問題（一般地每個(gè)子問題是互相關(guān)聯(lián)和影響的），再依次研究逐個(gè)問題的決策。決策就是某個(gè)階段的狀態(tài)確定后，從該狀態(tài)演變到下一階段狀態(tài)的選擇。當(dāng)全體子問題都解決時(shí)，整體問題也隨之解決。最優(yōu)子結(jié)構(gòu)性質(zhì)子問題重疊性質(zhì)

動(dòng)態(tài)規(guī)劃的解題思路是先把問題分成多個(gè)子問題（一般地每個(gè)子問題是互相關(guān)聯(lián)和影響的27最優(yōu)子結(jié)構(gòu)性質(zhì)一個(gè)最優(yōu)化策略的子策略總是最優(yōu)的。一個(gè)問題滿足最優(yōu)化原理又稱其具有最優(yōu)子結(jié)構(gòu)性質(zhì)。例如上圖中，若路線I和J是A到C的最優(yōu)路徑，則根據(jù)最優(yōu)化原理，路線J必是從B到C的最優(yōu)路線。這可用反證法證明：假設(shè)有另一路徑J'是B到C的最優(yōu)路徑，則A到C的路線取I和J'比I和J更優(yōu)，矛盾。從而證明J'必是B到C的最優(yōu)路徑。最優(yōu)子結(jié)構(gòu)性質(zhì)一個(gè)最優(yōu)化策略的子策略總是最優(yōu)的。一個(gè)問題滿足28子問題的重疊性動(dòng)態(tài)規(guī)劃的關(guān)鍵在于解決冗余，這是動(dòng)態(tài)規(guī)劃算法的根本目的。動(dòng)態(tài)規(guī)劃實(shí)質(zhì)上是一種以空間換時(shí)間的技術(shù)，它在實(shí)現(xiàn)的過程中，不得不存儲(chǔ)產(chǎn)生過程中的各種狀態(tài)，所以它的空間復(fù)雜度要大于其它的算法。選擇動(dòng)態(tài)規(guī)劃算法是因?yàn)閯?dòng)態(tài)規(guī)劃算法在空間上可以承受，而搜索算法在時(shí)間上卻無法承受，所以我們舍空間而取時(shí)間。子問題的重疊性動(dòng)態(tài)規(guī)劃的關(guān)鍵在于解決冗余，這是動(dòng)態(tài)規(guī)劃算法的29動(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)解。動(dòng)態(tài)規(guī)劃基本步驟找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。30思考與練習(xí)若城市路徑示意圖如下圖所示，

圖中，每條邊上的數(shù)字是通過這段道路所須的平均時(shí)間。條件：從A地出發(fā)，只允許向右或向上走。試尋找一條從A地到B地所需時(shí)間最短路徑和總時(shí)間。思考與練習(xí)若城市路徑示意圖如下圖所示，314、數(shù)塔問題

有形如下圖所示的數(shù)塔，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇向左走或是向右走，一直走到底層，要求找出一條路徑，使路徑上的值最大。4、數(shù)塔問題 有形如下圖所示的數(shù)塔，從頂32用暴力的方法，可以嗎？用暴力的方法，可以嗎？33 這道題如果用枚舉法（暴力思想），在數(shù)塔層數(shù)稍大的情況下（如31），則需要列舉出的路徑條數(shù)將是一個(gè)非常龐大的數(shù)目（2^30=1024^3>10^9=10億）。試想一下： 這道題如果用枚舉法（暴力思想），在數(shù)塔層數(shù)稍大的情況下（如34

拒絕暴力，倡導(dǎo)和諧～拒絕暴力，倡導(dǎo)和諧～35

從頂點(diǎn)出發(fā)時(shí)到底向左走還是向右走應(yīng)取決于是從左走能取到最大值還是從右走能取到最大值，只要左右兩道路徑上的最大值求出來了才能作出決策。 可見，由下層的子問題可以得到上層的子問題，所以，可從底層開始，層層遞進(jìn)，最后得到最大值。結(jié)論：自頂向下的分析，自底向上的計(jì)算。考慮一下： 從頂點(diǎn)出發(fā)時(shí)到底向左走還是向右走應(yīng)取決于是從左走能取到最365海盜盜寶問題海盜有一背包，能容納10公斤物品，現(xiàn)有三件寶物：重量分別是6，5，5公斤,價(jià)值分別是30萬，20萬，15萬請給出裝載方案，使背包價(jià)值達(dá)到最大。5海盜盜寶問題海盜有一背包，能容納10公斤物品370-1背包問題給定n種物品和一背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?目標(biāo)：使裝入背包中物品的總價(jià)值最大約束條件：裝入的物品總重不得超過C0-1背包問題給定n種物品和一背包。物品i的重量是w38海盜盜寶問題海盜有一背包，最大容積為9，現(xiàn)有5件寶物：體積si分別是2、3、4、5和4公斤價(jià)值vi分別是3、7、5、9和8請給出裝載方案，使背包價(jià)值達(dá)到最大。S1=2v1=3S2=3v2=7S3=4v3=5S4=5v4=9S5=4v5=8C=9海盜盜寶問題海盜有一背包，最大容積為9，現(xiàn)有5件寶39一開始，見物品就裝，物品1、2、3全裝入，背包裝滿了，得到背包總價(jià)值為15，這是不是最大價(jià)值呢？S1=2v1=3S2=3v2=7S3=4v3=5S4=5v4=9S5=4v5=8考慮只有前三個(gè)物品的情況一開始，見物品就裝，物品1、2、3全裝入，背包裝滿了，得到背40物品4該不該裝？有兩個(gè)選擇：（1）不裝，背包價(jià)值不變，為15S1=2v1=3S2=3v2=7S3=4v3=5S4=5v4=9（2）裝入，它占去的體積為5，得到價(jià)值為9，剩下容積4最多可以裝下多大價(jià)值？考慮只有前4個(gè)物品的情況物品4該不該裝？有兩個(gè)選擇：S1=2S2=3S3=4S4=541這是一個(gè)n=3(從前三個(gè)物品中選擇），容量c=4的子問題。目前最優(yōu)：裝入物品2和物品4，總價(jià)值為16若已知這個(gè)子問題的解是：裝物品2，得價(jià)值為7。S1=2v1=3S3=4v3=5S4=5v4=9（2）裝入物品4，它占去的體積為5，得到價(jià)值為9，剩下容積4最多可以裝下多大價(jià)值？S2=3v2=7這是一個(gè)n=3(從前三個(gè)物品中選擇），容量c=4的子問題。目42S1=2v1=3S3=4v3=5S4=5v4=9S5=4v5=8考慮5個(gè)物品的情況S2=3v2=7物品5該不該裝？(1)不裝，得到背包價(jià)值仍為16S1=2S3=4S4=5S5=4考慮5個(gè)物品的情況S2=3物43（2）若裝入物品5，占用體積為4，得價(jià)值為8，背包剩余容積為5。如何在前4個(gè)物品中選擇裝入，使背包價(jià)值最大化？這是n=4,c=5的一個(gè)子問題。若得到該子問題的解為：裝入物品1、2，得價(jià)值為10S1=2v1=3S3=4v3=5S5=4v5=8考慮5個(gè)物品的情況S2=3v2=7目前最優(yōu)：裝入物品5和1、2，總價(jià)值為18>16S4=5v4=9（2）若裝入物品5，占用體積為4，得價(jià)值為8，背包剩余容積為44子問題的構(gòu)造當(dāng)n=1時(shí):只有一個(gè)物品，s1=2,v1=3若背包容量c=0、1，則無法裝入物品1，得到背包價(jià)值為0若背包容量c=2、3、4、5、6，7，8，9則可裝入物品1，得到背包價(jià)值為3。C[1][0]=0C[1][1]=0C[1][2]=3C[1][3]=3C[1][4]=3C[1][5]=3C[1][6]=3C[1][7]=3C[1][8]=3C[1][9]=3子問題的構(gòu)造當(dāng)n=1時(shí):只有一個(gè)物品，s1=2,v1=3C45考慮兩個(gè)物品的情況當(dāng)n=2時(shí)，有兩個(gè)物品，s1=2,v1=3，s2=3,v2=7若背包容量c=0、1，得到背包價(jià)值為0若背包容量c=2，可裝入物品1，得總價(jià)值m[2][2]=3若背包容量c=3，m[2][3]=7若背包容量c=4,m[2][4]=7若背包容量c=5,m[2][5]=10若不裝物品2，m[2][3]=m[1][3]=3若裝入物品2，m[2][3]=v[2]+m[1][3-3]=7+0=7m[2][6]=10m[2][7]=10m[2][8]=10m[2][9]=10若不裝物品2，m[2][5]=m[1][5]=3若裝入物品2，m[2][5]=v[2]+m[1][5-3]=7+3=7考慮兩個(gè)物品的情況當(dāng)n=2時(shí)，有兩個(gè)物品，s1=2,v1=46遞推關(guān)系的建立用m[i][j]來表示從前i個(gè)物品中選取物品裝入容量為j的背包所得的最大價(jià)值。則要尋求的是m[n][c]。m[i][j]是以下兩個(gè)值的最大值

（1）m[i-1][j]:即不裝入物品i,背包價(jià)值與僅考慮前i-1個(gè)物品時(shí)情況相同；（2）v[i]+m[i-1][j-s[i]]:即裝入物品i,再從前i-1個(gè)物品中選取，使背包剩余容積j-s[i]價(jià)值最大化。遞推關(guān)系的建立用m[i][j]來表示從前i個(gè)物品中選取物品裝47構(gòu)造價(jià)值數(shù)組S1=2v1=3S2=3v2=7S3=4v3=5S4=5v4=9S5=4v5=80123456789000000000001020304050背包容量j從前i個(gè)物品中選取構(gòu)造價(jià)值數(shù)組S1=2S2=3S3=4S4=5S5=4012348S1=2v1=3S2=3v2=7S3=4v3=5S4=5v4=9S5=4v5=8012345678900000000000100333333332003771010101010300377101012121540037710101216165018背包容量j從前i個(gè)物品中選取S1=2S2=3S3=4S4=5S5=4012345678949構(gòu)造最優(yōu)解0123456789000000000001003333333320037710101010103003771010121215400377101012161650037