講義案例信息學section3.2.0text knapsack problems

1、SECTION3.2.0 TEXT: KNAPSACK PROBLEMS背包問題譯 by 銘，背包問題一般是這樣描述的：設(shè)n 個重量為（W1,W2,.Wn）的物品和一個載重為（S 的背包，將物品的一部分xi 放進背包中的利潤是Pixi，問如何選擇物品的種類和數(shù)量，使得背包裝滿而獲得最大的利潤？另有一簡化版本說：設(shè)有一個背包可以放入的物品重量為 S，現(xiàn)有 n 件物品，重量分別為 W1,W2,.Wn。問能否從這 n 件物品中選擇若干件放入此背包，使得放入的重量之和正好為S。-譯者加，不知道有沒有班門弄斧之嫌）前提貪心法（它是一種多步?jīng)Q策法，它總是作出在當前看來是最好的選擇，它的考慮不是從整體出發(fā)，

2、而只是某種意義上的局部最優(yōu)，這樣貪心法不能對所有問題達到整體最優(yōu)解，但是對相當范圍的許多問題都能夠產(chǎn)生整體最優(yōu)解。-譯者）動態(tài)規(guī)劃（它是將問題進行逐步的劃分來縮小問題的規(guī)模，直到可以求出子問題的解為止。分劃子問題后，對應(yīng)的子問題中解決，并將解保存起來，以備后面-譯者）遞歸下降的重復，這樣就將重復地求解；在第一次遇到重復時把它。動態(tài)規(guī)劃法常用來求一個問題在某種意義下的最優(yōu)解。示例問題：用帶最喜歡的是制作一個Bessie 喜歡的音樂合集磁帶以便它在產(chǎn)奶時聽。Bessie農(nóng)場主的產(chǎn)奶量取決于它產(chǎn)奶時所聽的歌曲。已知一組歌曲（每首歌都由一對整數(shù)此曲的長度（以秒計），聽該首歌時的產(chǎn)奶量來表示）以及給擠奶

3、的總時間。找到這樣一組歌曲的集合，使得歌曲的總長度不超過給 Bessie 擠奶的總時間且使Bessie 的產(chǎn)奶量達到最大。抽象描述已知一組物品-每個都有其尺寸和值（比如，重量），以及可用的總空間。找到這樣一個集合，使得該集合的值的和最大，且其尺寸的和受某些限制所約束。集合中任何一個特定的項目的總數(shù)目/尺寸過它的可利用率。解題想法視其為背包問題的一般方法是一個容量受限的背包使得放入其中的物品的值達到最大。以上述問題為例，Bessie 產(chǎn)奶時聽的音樂帶就是“背包”，而那些歌就是“放入背包中的物品”。三個背包問題背包問題有三種形式：小數(shù)背包問題允許將小數(shù)表示的物品放入背包中的是小數(shù)背包問題。舉例來說

4、，如果物品是原油、飛機、煤油而你的背包是一只水桶，取 0.473 升的原油，0,263 升的飛機有意義的。這是形式最簡單的要解決的背包問題。整數(shù)背包問題和 0,264 升的煤油就是在整數(shù)背包問題中，只有完整的物品能放入背包里。此形式的一個例子就是：部分的曲子不允許放入包中。多重背包問題在多重背包問題中，需被填充的背包多于一個。如果允許有小數(shù)的物品放入，也就等于有一個大的背包，其容量相當于所有可用背包的和。因此，此術(shù)語只用來指多重整數(shù)背包的情況。小數(shù)背包問題小數(shù)背包問題是三者中最簡單的，其貪婪解法如下：找到“值密度”（物品值/尺寸）最大的物品如果總?cè)萘咳跃统^物品的可利用率，把所有滿足條件的物品

5、放入背包中，然后反復執(zhí)行。如果總?cè)萘可儆谖锲返目衫寐?，盡可能多的使用可用空間，然后終止。由于這個算法必須先按照值密度把物品分類，然后以降序?qū)⑺鼈兎湃氡嘲敝寥萘坑猛?，該算法以N log N 級運行。通常簡單些的方法不是將它們分類，而是不停地找每次不用的最大值密度，這種算法的時間復雜度是O(N 2) 。注意：對于這類問題，因為你可以做一個微小的變換使得所有的物品尺寸大小為一，且原始尺寸大小和可利用率（當然用原始尺寸大小除值）的乘積就是總?cè)萘?，同時有尺寸和可利用率是很少見的。延伸：在這種情況下，物品的值和可利用率可以是實數(shù)。用這種算法處理有小數(shù)的尺寸大小也不是問題。整數(shù)背包問題這個問題有點難度

6、，但是如果背包足夠小，使用動態(tài)規(guī)劃，它還是可解的。依據(jù)背包大小的最大值設(shè)計動態(tài)的程序。刷新用來表示大小為S 的物品的數(shù)組，顛倒其次序，看將當前物品放入大小為 K 的背包中所產(chǎn)生的集合是否比當前最好的大小為K+S 的背包更符合條件。這個算法運行K*N 次，其中K 是背包的大小，N 是物品的可利用率義之和。如果背包太大了以至于無法分配此數(shù)組，遞歸下降是一種選擇，即這個問題是 NP 完全的（給定I 上的一個語言L，如果有一架非確定圖靈機M 和一個多項式P(n)，對任何 I 上的長度為n的串w，M 都可以在P(n)確定是否接受w，則稱 L 是非確定圖靈機下多項式時間復雜性問題，簡記為 NP 問題/語言

7、。若L 是屬于 NP 的，且對 NP 中的每一個語言 L，都存在一個從 L至L 的多項式時間轉(zhuǎn)化，說L 是 NP 完整的。-譯者）。當然，遞歸下降在以小的物品填充的大背包情況下可以運行相當長的一段時間。延伸：小數(shù)的值不是問題；數(shù)組可以用實數(shù)數(shù)組來代替整數(shù)數(shù)組。小數(shù)的可利用率并不影響什么，在沒有大量損失的條件下，縮短數(shù)字（如果你有 3,5 個物品，你可以僅用 3）。小數(shù)的尺寸是個討厭的東西，它使得問題遞歸下降。如果尺寸都相同，問題就能貪婪地解開，在下降的值排序中選擇物品，直到背包滿為止。如果值都是 1.0，同樣地使用貪心法，在上升的尺寸大小排序中選擇物品，直到背包滿為止。多重背包問題對于任何大小

8、的多重背包，狀態(tài)空間太大了以至于無法使用從整數(shù)背包算法中來的 DP 解法。于是遞歸下降是解決這個問題的方法。延伸：用遞歸下降，通常擴展就簡單了。小數(shù)的尺寸和值就不是問題了，同樣地值的計算功能也不是問題。如果值都是同一個，那么如果能被放入所有背包中的物品的最大值是n，則存在使用n 個最小物品的解法。它能大大減少查找時間。示例問題分數(shù)膨脹1998 USACO National Chionship你正試圖設(shè)計一個有最高分數(shù)(10,000)的比賽。已知比賽長度，一組問題，問題的長度以及每個問題的分值，計算滿足長度約束的最高分數(shù)的比賽。分析：這是一個整數(shù)背包問題，比賽是背包，尺寸是問題的長度，值是分數(shù)值。背包（比賽）尺寸的限制是其足夠小使得解法在器中運行。欄1999 USACO Spring Open農(nóng)場主準備在他的領(lǐng)地建一圈。他已裝好了柱子，所以他知道所要的圍欄長度。當?shù)氐哪静牡暧懈鞣N長度的木板（至多 50 個）。已知木材店木板的長度，要的圍欄長度，計算約翰建所用的圍欄最大值。分析：這是個多重背包問題，木材店的木板是背包，物品是值是一。用的圍欄。物品的尺寸就是長度，由于值都是一，如果存在用任意K 個圍欄的解法，則有用K 個最小圍欄的解法