目錄

• 1.問題描述
  1.1 問題描述
  1.2 問題的數(shù)學(xué)表示（規(guī)劃類問題，此種表示可以轉(zhuǎn)換為回溯法）
  1.3 三種方法的比較
• 2.動(dòng)態(tài)規(guī)劃
  2.1 刻畫一個(gè)最優(yōu)解的結(jié)構(gòu)特征（最優(yōu)子結(jié)構(gòu)）
  2.2 遞歸地定義最優(yōu)解的值（重疊子問題）
  2.3 計(jì)算最優(yōu)解的值，通常采用自底向上的方法
  2.4 利用計(jì)算出的信息構(gòu)造一個(gè)最優(yōu)解
• 3.回溯法
  3.1 01背包問題的數(shù)學(xué)描述
  3.2 用回溯法搜索解空間
  3.3 一個(gè)示例
• 4.分支限界法
  4.1 分支限界法解決0-1背包問題
  4.2 一個(gè)示例
• 5.可以轉(zhuǎn)換為0-1背包問題的雙核問題
  5.1 題目描述
  5.2 轉(zhuǎn)化為背包問題

1.問題描述

1.1 問題描述

假定n個(gè)商品重量分別為w₀, w₁, ..., w_n-1，價(jià)值分別為p₀, p₁, ..., p_n-1，背包載重量為M。怎樣選擇商品組合，使得價(jià)值最高？

1.2 問題的數(shù)學(xué)表示（規(guī)劃類問題，此種表示可以轉(zhuǎn)換為回溯法）

• 假設(shè)x_i表示商品i被裝入背包的情況，x_i = 0,1。根據(jù)題目要求，有如下約束方程和目標(biāo)函數(shù)：
  
• 問題歸結(jié)為尋找一個(gè)滿足上述約束方程并使目標(biāo)函數(shù)達(dá)到最大的解向量X = (x₁, x₂, ..., x_n)。

1.3 三種方法的比較

• 動(dòng)態(tài)規(guī)劃通過最優(yōu)子結(jié)構(gòu)，將問題轉(zhuǎn)換為子問題的求解。轉(zhuǎn)換的過程中，涉及到某個(gè)具體的商品是否選擇的問題。
• 回溯法根據(jù)數(shù)學(xué)表達(dá)式，搜索解向量(x₁, x₂, ..., x_n)的整個(gè)解空間
  搜索的時(shí)候利用貪心性質(zhì)（按照單位重量價(jià)值遞減排序，估算可能的最高上界）、以及已經(jīng)計(jì)算出的可行解作為界限進(jìn)行剪枝。
  但是回溯法，原則上要窮盡所有可能，只不過是對(duì)有些分支提前返回了。
• 分支限界法
  剪枝方法同回溯法是一樣的：利用貪心性質(zhì)（按照單位重量價(jià)值遞減排序，估算可能的最高上界）、以及已經(jīng)計(jì)算出的可行解作為界限進(jìn)行剪枝。
  唯一的不同是，分支限界法利用的是優(yōu)先隊(duì)列，并且，當(dāng)針對(duì)一個(gè)結(jié)點(diǎn)進(jìn)行擴(kuò)展時(shí)，會(huì)將所有兒子結(jié)點(diǎn)進(jìn)行展開，計(jì)算出所有兒子結(jié)點(diǎn)所能達(dá)到的最高上界。因此，當(dāng)一個(gè)優(yōu)先隊(duì)列中首結(jié)點(diǎn)是一個(gè)可行解，則結(jié)束。
• 因此，可以看出回溯法與分支限界法的本質(zhì)不同是在于搜索解空間的遍歷方式不同。
  回溯法是深度優(yōu)先，要窮盡解空間的所有可能，找到最優(yōu)解。
  分支限界法是廣度優(yōu)先，本質(zhì)上也是窮盡了解空間的所有可能，找到最優(yōu)解。

2.動(dòng)態(tài)規(guī)劃

2.1 刻畫一個(gè)最優(yōu)解的結(jié)構(gòu)特征（最優(yōu)子結(jié)構(gòu)）

• 假設(shè)01背包問題的一個(gè)最優(yōu)解為S，其中i為序號(hào)最大的商品；
  那么S' = S - {i}必然是M - w_i的最優(yōu)解
  證明方法可以采用cut-paste方法進(jìn)行證明

2.2 遞歸地定義最優(yōu)解的值（重疊子問題）

• 定義c[i, w]為商品1,....,i，最大重量為w的最優(yōu)解（最大價(jià)值）。那么就有以下兩種情況：
• 如果w_i > w，c[i, w]轉(zhuǎn)化為求解一個(gè)子問題c[i-1, w]；
• 如果w_i ≤ w，c[i, w]轉(zhuǎn)換成了求解兩個(gè)子問題：
  一個(gè)包含商品i，p_i + c[i-1, w- w_i]；
  一個(gè)不包含商品i，c[i-1, w]；
  兩種情況中的較大者即為c[i, w]
• （重疊子問題）很顯然c[i-1, w-w_i]與c[i-1, w]有重疊子問題。
  

2.3 計(jì)算最優(yōu)解的值，通常采用自底向上的方法

• 如下動(dòng)態(tài)規(guī)劃方法的運(yùn)行時(shí)間為Θ(nM)

  
  
  動(dòng)態(tài)規(guī)劃計(jì)算方法

2.4 利用計(jì)算出的信息構(gòu)造一個(gè)最優(yōu)解

• 如果c[i, w] = p_i + c[i-1, w-w_i]，則i是答案的一部分；否則便不是。

3.回溯法

3.1 01背包問題的數(shù)學(xué)描述

• 假設(shè)x_i表示商品i被裝入背包的情況，x_i = 0,1。根據(jù)題目要求，有如下約束方程和目標(biāo)函數(shù)：
  
• 問題歸結(jié)為尋找一個(gè)滿足上述約束方程并使目標(biāo)函數(shù)達(dá)到最大的解向量X = (x₁, x₂, ..., x_n )。

3.2 用回溯法搜索解空間

3.2.1 解空間

• 很顯然，解空間為一棵高度為n的完全二叉樹。所有解的可能性為所有的葉子節(jié)點(diǎn)，總共有2ⁿ種。

3.2.2 剪枝的方法（根據(jù)約束條件和bound來進(jìn)行剪枝）

• 上界bound = 0
• 假定第i層左兒子表示商品i被裝入背包，右兒子表示未被裝入背包
• 將物體按照價(jià)值重量比的非增順序排序，然后按照這個(gè)順序搜索，在搜索過程中，盡量沿著左兒子繼續(xù)前進(jìn)。
• 當(dāng)不能沿著左兒子繼續(xù)前進(jìn)時(shí)，得到問題的一個(gè)部分解，并把搜索轉(zhuǎn)移到右子樹。此時(shí)，估計(jì)由這個(gè)部分解所能得到的最大價(jià)值，把該值與當(dāng)前的上界進(jìn)行比較，如果高于上界，就繼續(xù)在右子樹上搜索，知道找到一個(gè)可行解，用可行解的值刷新上界bound。
• 向上回溯，尋找其他可行解。如果部分解所估計(jì)的最大值小于當(dāng)前的上界，就丟棄當(dāng)前正在搜索的部分解，直接向上回溯。

最大值的估算法（跟分支限界法本質(zhì)上是一樣的）

• 假定當(dāng)前解是{x₀, x₁, ..., x_k-1 }
  

向上回溯的方法

• 如果當(dāng)前的結(jié)點(diǎn)是左兒子分支結(jié)點(diǎn)，就轉(zhuǎn)而搜索相應(yīng)的右兒子分支結(jié)點(diǎn)；
• 如果當(dāng)前的結(jié)點(diǎn)是右兒子分支結(jié)點(diǎn)，就沿著右兒子分支結(jié)點(diǎn)向上回溯，知道左兒子分支結(jié)點(diǎn)為止，然后再轉(zhuǎn)而搜索相應(yīng)的右兒子分支結(jié)點(diǎn)

3.2.3 回溯法的步驟描述

w_cur——表示當(dāng)前正在搜索的部分解中轉(zhuǎn)入的總重量
p_cur——當(dāng)前總價(jià)值
p_est——部分解可能達(dá)到的最大價(jià)值的估計(jì)值
p_total——當(dāng)前搜索到的所有可行解中的最大價(jià)值，是當(dāng)前目標(biāo)函數(shù)的上界
y_k、x_k——部分解的第k個(gè)分量及其副本
k——表示當(dāng)前搜索深度

• step1.按商品價(jià)值重量比的非增排序排序
• step2.w_cur、p_cur和p_total初始化為0，把部分解初始化為空，k=0
• step3.從當(dāng)前的部分解可取得的最大價(jià)值p_est
• step4.若p_est > p_total，轉(zhuǎn)step5；否則，轉(zhuǎn)step8
• step5.從v_k開始把商品裝入背包，直到?jīng)]有商品可裝貨裝不下v_i為止，并生成部分解y_k, ..., y_i，k ≤ i < n，刷新p_cur
• step6.如果i ≥ n，得到一個(gè)新的可行解，把所有的y_i復(fù)制給x_i，p_total = p_cur，p_total是目標(biāo)函數(shù)的新界；令k = n，轉(zhuǎn)step3，以便回溯搜索其他的可能解
• step7.否則，得到一個(gè)部分解，令k=i+1，舍棄商品v_i，從商品v_i+1繼續(xù)裝入，轉(zhuǎn)step3.
• （回溯）step8.當(dāng)i ≥ 0且y_i為0時(shí)，執(zhí)行i = i -1，直到y(tǒng)_i ≠ 0為止；即沿右兒子分支結(jié)點(diǎn)方向回溯，直到左兒子分支結(jié)點(diǎn)。
• step9.如果i < 0，算法結(jié)束，否則，轉(zhuǎn)step10
• step10.令y_i = 0，w_cur = w_cur - w_i, p_cur = p_cur - p_i, k = i + 1，轉(zhuǎn)step3；從左兒子分支結(jié)點(diǎn)轉(zhuǎn)移到相應(yīng)的右兒子分支結(jié)點(diǎn)，繼續(xù)搜索其他的部分解或可能解。

3.3 一個(gè)示例

M = 50
商品重量分別為5,15,25,27,30
商品價(jià)值分別為12,30,44,46,50
上面已經(jīng)按照單位重量價(jià)值遞減順序排列。

4.分支限界法

4.1 分支限界法解決0-1背包問題

• 按價(jià)值重量比 遞減 的順序，對(duì)n個(gè)商品進(jìn)行排序
  排序后商品序號(hào)的結(jié)合為S = {0, 1, ..., n-1}
• 將這些商品分為3個(gè)集合：
  S₁——選擇裝入背包的商品集合
  S₂——不選擇裝入背包的商品集合
  S₃——尚待選擇的商品集合
• S₁(k)、S₂(k)、S₃(k)分別表示在搜索深度為k時(shí)的3個(gè)集合中的商品。開始時(shí)有：
  S₁(0) = ?
  S₂(0) = ?
  S₃(0) = {0, 1, ..., n-1}

4.1.1 分支方法（二叉分支）

• 假設(shè)比值p_i/w_i最大的商品序號(hào)為s（s ∈ S₃），用s進(jìn)行分支，一個(gè)分支結(jié)點(diǎn)表示把商品s裝入背包，另一個(gè)分支結(jié)點(diǎn)表示不把商品s裝入背包。
  當(dāng)商品按照價(jià)值重量比遞減排序后，s就是集合S₃(k)中的第一個(gè)元素。特別地，當(dāng)搜索深度為k時(shí)，商品s的序號(hào)就是集合S中的元素k。
• 把商品s裝入背包的分支結(jié)點(diǎn)
  S₁(k+1) = S₁(k) ∪ {k}
  S₂(k+1) = S₂(k)
  S₃(k+1) = S₃(k) - {k}
• 不把商品s裝入背包的分支結(jié)點(diǎn)
  S₁(k+1) = S₁(k)
  S₂(k+1) = S₂(k) ∪ {k}
  S₃(k+1) = S₃(k) - {k}

4.1.2 上界估算方法（按照單位價(jià)值最大進(jìn)行貪心選擇）

• 假定b(k)表示在搜索深度為k時(shí)，某個(gè)分支結(jié)點(diǎn)的背包中商品的價(jià)值上界。
  此時(shí)S₃(k) = {k, k+1, ..., n-1}。用如下方法計(jì)算兩種分支結(jié)點(diǎn)背包中商品價(jià)值的上界：
  
• 上述公式的理解
  1）按照一個(gè)商品是否加入到S₁集合，總共有2ⁿ個(gè)葉子節(jié)點(diǎn)，每個(gè)葉子節(jié)點(diǎn)對(duì)應(yīng)一種情況
  2）當(dāng)一層一層向下搜索是，如果當(dāng)前S₁集合中的總重量超過了載重量M，則直接將b(k)置為0，該分支終止。
  為什么這樣做？因?yàn)樵谒阉魃弦粚訒r(shí)，該商品不應(yīng)該加入到S₁集合，這種不加入該商品情況對(duì)應(yīng)于另一個(gè)分支。加入該商品的此分支已經(jīng)不滿足要求了，所以剪枝。

4.1.3 分支限界法求解步驟

每個(gè)結(jié)點(diǎn)都包含如下信息：
??S₁——當(dāng)前選擇裝入背包的商品集合
??S₂——當(dāng)前不選擇裝入背包的商品集合
??S₃——當(dāng)前尚待選擇的商品集合
??k——搜索深度
??b——上界
bound——一個(gè)可行解的取值，當(dāng)做剪枝的標(biāo)準(zhǔn)

• step1.bound = 0，把商品按價(jià)值重量比遞減排序
• step2.建立根節(jié)點(diǎn)X
  X.b = 0
  X.k = 0
  X.S₁ = ?
  X.S₂ = ?
  X.S₃ = S
• step3. 若X.k == n，算法結(jié)束，X.S₁即為裝入背包中的物體，X.b即為裝入背包中物體的最大價(jià)值；
  否則轉(zhuǎn)向step4
• （分支1）step4.建立結(jié)點(diǎn)Y
  Y.S₁ = X.S₁ ∪ {X.k}
  Y.S₂ = X.S₂
  Y.S₃ = X.S₃ - {X.k}
  Y.k = X.k + 1
  計(jì)算Y.b，將Y.b與bound進(jìn)行比較，據(jù)此判定是否插入優(yōu)先隊(duì)列；當(dāng)S₃為空時(shí)，找到一個(gè)可行解，判定是否更新bound。
• （分支2）step5.建立結(jié)點(diǎn)Z
  Z.S₁ = X.S₁
  Z.S₂ = X.S₂ ∪ {X.k}
  Z.S₃ = X.S₃ - {X.k}
  Z.k = Z.k + 1
  計(jì)算Z.b，將Z.b與bound進(jìn)行比較，據(jù)此判定是否插入優(yōu)先隊(duì)列；當(dāng)S₃為空時(shí)，找到一個(gè)可行解，判定是否更新bound。
• step6.取出優(yōu)先隊(duì)列首元素作為結(jié)點(diǎn)X，轉(zhuǎn)向step3

4.2 一個(gè)示例

• 有5個(gè)商品，重量分別為8,16,21,17,12，價(jià)值分別為8,14,16,11,7，背包的載重量為37，求裝入背包的商品及其價(jià)值。

  
  

5.可以轉(zhuǎn)換為0-1背包問題的雙核問題

5.1 題目描述

一種雙核CPU的兩個(gè)核能夠同時(shí)的處理任務(wù)，現(xiàn)在有n個(gè)已知數(shù)據(jù)量的任務(wù)需要交給CPU處理，假設(shè)已知CPU的每個(gè)核1秒可以處理1kb，每個(gè)核同時(shí)只能處理一項(xiàng)任務(wù)。n個(gè)任務(wù)可以按照任意順序放入CPU進(jìn)行處理，現(xiàn)在需要設(shè)計(jì)一個(gè)方案讓CPU處理完這批任務(wù)所需的時(shí)間最少，求這個(gè)最小的時(shí)間

輸入描述:

輸入包括兩行： 第一行為整數(shù)n(1 ≤ n ≤ 50) 第二行為n個(gè)整數(shù)length[i](1024 ≤ length[i] ≤4194304)，表示每個(gè)任務(wù)的長度為length[i]kb，每個(gè)數(shù)均為1024的倍數(shù)。

輸出描述:

輸出一個(gè)整數(shù)，表示最少需要處理的時(shí)間

輸入例子:

5 3072 3072 7168 3072 1024

輸出例子:

9216

5.2 轉(zhuǎn)化為背包問題

• 最小時(shí)間的意思即兩個(gè)核同時(shí)滿負(fù)荷運(yùn)行，并且當(dāng)兩個(gè)核所處理的任務(wù)量都接近于總?cè)蝿?wù)量M的一半時(shí)，時(shí)間最少
• 因此題目轉(zhuǎn)換為：對(duì)于其中一個(gè)核，假設(shè)其任務(wù)量為上限M/2，在所有這些任務(wù)中選擇一個(gè)處理組合，使得這些任務(wù)組合在不超過M/2的情況下達(dá)到最大
• 因此本質(zhì)上就是一個(gè)背包問題，背包的容量為M/2，商品的單位重量價(jià)值均為1，商品的重量即為任務(wù)所需要的時(shí)間量。