關於背包成績的一些懂得和運用。本站提示廣大學習愛好者：（關於背包成績的一些懂得和運用）文章只能為提供參考，不一定能成為您想要的結果。以下是關於背包成績的一些懂得和運用正文
1.背包成績引見
背包成績不單單是一個簡略的算法成績，它實質上代表了一年夜類成績，這類成績現實上是01線性計劃成績，其束縛前提和目的函數以下：
自從dd_engi在2007年推出《背包成績九講》以後，背包成績的重要精華根本已道盡。本文沒有測驗考試對背包成績的實質停止擴大或深刻發掘，而只是從無限的懂得（這裡指對《背包成績九講》的懂得）動身，贊助讀者更快地進修《背包成績九講》中的提到的各類背包成績的重要算法思惟，並經由過程實例說明了響應的算法，同時給出了幾個背包成績的經典運用。
2.背包成績及運用
dd_engi在《背包成績九講》中重要提到四種背包成績，分離為：01背包成績，完整背包成績，多重背包成績，二維費用背包成績。本節總結了這幾種背包成績，並給出了其典范的運用以贊助讀者懂得這幾種成績的實質。
2.101背包成績
（1）成績描寫
有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可以使價值總和最年夜。
（2）狀況轉移方程
個中，f(i,v) 表現早年i件物品選擇若干物品裝到容量為v的背包中發生的最年夜價值。當v=0時，f(i,v)初始化為0，表現標題不請求背包必定恰好裝滿，而f(i,v)=inf/-inf（正無限或負無限）表現標題請求背包必定要恰好裝滿。上面幾種背包相似，今後不再贅述。
（3） 偽代碼
從轉移方程上可以看出，前i個物品的最優解只依附於前i-1個物品最優解，而與前i-2，i-3,…各物品最優無直接關系，可以應用這個特色優化存儲空間，即只請求一個一維數組便可，算法時光龐雜度（O(VN)）為:
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
留意v的遍歷次序！！！
上面幾種背包用到相似優化，今後不再贅述。
（4） 舉例
V=10，N=3，c[]={3,4,5}, w={4,5,6}
（1）背包紛歧定裝滿
盤算次序是：從右往左，自上而下：
（2）背包恰好裝滿
盤算次序是：從右往左，自上而下。留意初始值，個中-inf表現負無限
（5） 經典題型
[1] 你有一堆石頭質量分離為W1,W2,W3…WN.(W＜＝100000,N <30)如今須要你將石頭歸並為兩堆，使兩堆質量的差為最小。
[2] 給一個整數的聚集，要把它分紅兩個聚集，要兩個聚集的數的和最接近
[3] 有一個箱子容量為V（正整數，0≤V≤20000），同時有n個物品（0小於n≤30），每一個物品有一個別積（正整數）。請求從n個物品中，任取若干個裝入箱內，使箱子的殘剩空間為最小。
2.2完整背包成績
（1）成績描寫
有N種物品和一個容量為V的背包，每種物品都有沒有限件可用。第i種物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可以使這些物品的費用總和不跨越背包涵量，且價值總和最年夜。
（2）狀況轉移方程
或許：
（3） 偽代碼
for i=1..N
for v=0..V
f[v]=max{f[v],f[v-c[i]]+w[i]};
留意v的遍歷次序！！！
留意，時光龐雜度仍為：O(VN).
（4） 舉例
V=10，N=3，c[]={3,4,5}, w={4,5,6}
（1）背包紛歧定裝滿
盤算次序是：從左往右，自上而下：
（2）背包恰好裝滿
盤算次序是：從左往右，自上而下。留意初始值，個中-inf表現負無限
（5） 經典題型
[1] 找零錢成績：有n種面額的硬幣，每種硬幣無窮多，至多用若干枚硬幣表現給定的面值M？
2.3多重背包成績
（1）成績描寫
有N種物品和一個容量為V的背包。第i種物品最多有n[i]件可用，每件費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可以使這些物品的費用總和不跨越背包涵量，且價值總和最年夜。
（2）狀況轉移方程
（3） 解題思惟
用以下辦法轉化為通俗01背包成績：將第i種物品分紅若干件物品，個中每件物品有一個系數，這件物品的費用和價值均是本來的費用和價值乘以這個系數。使這些系數分離為 1,2,4,…,2^(k-1),n[i]-2^k+1，且k是知足n[i]-2^k+1>0的最年夜整數。例如，假如n[i]為13，就將這類 物品分紅系數分離為1,2,4,6的四件物品。這類辦法能包管關於0..n[i]間的每個整數，都可以用若干個系數的和表現。這個很輕易證實，證實進程頂用到以下定理：任何一個整數n都可以表現成：n=a0*2^0+a1*2^1+…+ak*2^k,個中ak=0或許1(現實上就是n的二進制分化)，
定理：一個正整數n可以被分化成1,2,4,…,2^(k-1),n-2^k+1（k是知足n-2^k+1>0的最年夜整數）的情勢，且1～n以內的一切整數都可以獨一表現成1,2,4,…,2^(k-1),n-2^k+1中某幾個數的和的情勢。
該定理的證實以下：
（1） 數列1,2,4,…,2^(k-1),n-2^k+1中一切元素的和為n，所以若干元素的和的規模為：[1, n]；
（2）假如正整數t<= 2^k – 1,則t必定能用1,2,4,…,2^(k-1)中某幾個數的和表現，這個很輕易證實：我們把t的二進制表現寫出來，很顯著，t可以表現成n=a0*2^0+a1*2^1+…+ak*2^（k-1），個中ak=0或許1，表現t的第ak位二進制數為0或許1.
（3）假如t>=2^k,設s=n-2^k+1，則t-s<=2^k-1，因此t-s可以表現成1,2,4,…,2^(k-1)中某幾個數的和的情勢，進而t可以表現成1,2,4,…,2^(k-1)，s中某幾個數的和（加數中必定含有s）的情勢。
（證畢！）
該算法的時光龐雜度為：O(V*sum(logn[i])).
（4） 經典題型
[1] 找零錢成績：有n種面額的硬幣，分離為a[0], a[1],…, a[n-1]，每種硬幣的個數為b[0], b[1],…, b[n-1]，至多用若干枚硬幣表現給定的面值M？
2.4二維費用背包
（1）成績描寫
二維費用的背包成績是指：關於每件物品，具有兩種分歧的費用；選擇這件物品必需同時支付這兩種價值；關於每種價值都有一個可支付的最年夜值（背包涵量）。問 如何選擇物品可以獲得最年夜的價值。設這兩種價值分離為價值1和價值2，第i件物品所需的兩種價值分離為a[i]和b[i]。兩種價值可支付的最年夜值（兩種 背包涵量）分離為V和U。物品的價值為w[i]。
（2）狀況轉移方程
（3）算法思惟
采取統一維情形相似的辦法求解
（4）經典題型
有2n個整數，均勻分紅兩組，每組n個數，使這兩組數的和最接近。
3.背包總結
背包成績現實上代表的是線性計劃成績，普通要斟酌以下幾個身分已決議拔取甚麼樣的算法：
（1）束縛前提，有一個照樣兩個或許更多個，假如是一個，能夠是01背包，完整背包或許多重背包成績，假如有兩個束縛前提，則能夠是二維背包成績。
（2）優化目的，求最年夜值，照樣最小值，照樣總數(只需將max換成sum)
（3）每種物品的個數限制，假如每種物品只要一個，只是簡略的01背包成績，假如個數無窮制，則是完整背包成績，假如每種物品的個數無限制，則是多重背包成績。
（4）背包能否請求恰好塞滿，留意不塞滿和塞滿兩種情形下初始值分歧。
4.參考材料
dd_engi：《背包成績九講》
