Advanced Algorithm - Knapsack Problem

背包問題為一個典型的最佳化問題，想像你來到了一個寶庫，裡頭有一些寶物，都有各自的價值和重量，但你只帶了一個背包(而且負重還有限制)，要怎麼取寶物才能在背得走的前提下，帶走價值總和儘可能高的寶物們呢？

這裡我們考慮最基本的 0/1 - Knapsack Problem 。簡單的 formulation 如下:

We have $n$ items, each one with value $v_i$ and weight $w_i$. The weight limit of the backpack is $W$.

2-Approx Algorithm

若今天物品是可分割的話，有一個簡單的 greedy 方法可以找到最佳解 (依據$\frac{v_i}{w_i}$作排序，選擇單位重量價值最高的物品，塞到背包塞不下為止)。而在 0/1 - Knapsack 中，也可利用此方法找到 2-Approx 的解。

Algorithm

Sort items according to $\frac{v_i}{w_i}$ in decending order. Choose items in that order until constraint DOESN'T satisfy, then pick $max(v_1 + v_2 + \cdots +v_i,$ $v\scriptstyle{i+1}$$)$

DP-based Algorithm

概念是給定欲達到的價值($v$)，從物品的子集(item 1 ~ i)中，找到所需重量最小的物品集合之重量 ( $A[i,v]$ )

Algorithm

Let $A[i,v]$: min. weight chosen from items 1 ~ i such that $\sum \text{value} \geq v$

initial condition: $A[0,v] = (v \leq 0,)?,0:\infty$

recursive relation: $A[i,v] = \min(\stackrel{\textcolor{blue}{i,\text{is not picked}}}{A[i-1,v]},\stackrel{\textcolor{blue}{i,\text{is picked}}}{A[i-1,v-v_i]+w_i})$

Then search the n-th column (along the value axis),
we can find $v^{\star} ; \text{such that}; A[n,v^{\star}] \leq W \land A[n,v^{\star}+1] > W$

The time complexity is $\Theta(n , v^{\star})$

然而，我們已知 Knapsack Problem 為 NPC 問題，目前並不存在已知的 polynomial-time 的解法，但為何 DP 的複雜度卻不是指數呢？

Psuedo-Poly Algorithm [Weakly NP-Hard]

Running time is poly. in the input size under unary representation (not binary $\uparrow$)

一般而言，我們會以二進位制儲存數字，所以 input size 應為 $\sum \log{v_i} + \sum \log{w_i}$，然而方才的演算法卻會一個一個地掃過 value axis ，直到找到解為止，最壞情況下($W$相當寬鬆)，複雜度為 $\Theta(n , \sum{v_i})$
$\Rightarrow$ Running time 為 input 的指數。\
(另外，若想用 unary representation 來儲存 instance ，付出的代價即是空間複雜度變為 原先input size 的指數)

Strong NP-Hard

NP-Hard even all numerical values are POLY(sizeof input) e.g Exactly Set Cover

(1+ $\epsilon$)-Approx Algorithm

剛剛 DP 的方法壞就壞在必須線性掃過 value axis, 我們是否能過不要檢查每一個 $v$ ，而是跳著檢查某些 $v$ 值就好了呢？從上述的直覺，發展出 rounding 這個 scheme，犧牲一些精確度($1,+, \epsilon$)，將複雜度壓回 polynomial。

Algorithm

Let $b = \frac{\epsilon}{2n}\max_i v_i$

Now, consider the rounded instance $\text{0-1 Knapsack}^{\prime}$ , $\hat{w_i} = w_i , , \hat{W} = W , , \textcolor{blue}{\hat{v_i} = \lceil \frac{v_i}{b} \rceil \cdotp b}$

$\Rightarrow$ Running time for solving $\text{0-1 Knapsack}^{\prime}$ is $\Theta(n \cdotp \frac{v^{\star}}{b}) = \Theta(\frac{n^3}{\epsilon})$

Correctness Check

value(OPT) in 0-1 Knapsack\
$\leq$ value(OPT) in $\text{0-1 Knapsack}^{\prime}$ $(\because$ 進位)\
$\leq \text{value}$ ($\text{OPT}^{\prime}$) in $\text{0-1 Knapsack}^{\prime}$ \
$\leq \text{value}$ ($\text{OPT}^{\prime}$) in 0-1 Knapsack + $nb$ (直接就加一 個刻度)\
= value($\text{OPT}^{\prime}$) + $\frac{\epsilon}{2} \underset{\textcolor{blue}{\leq \text{value(OPT)}}}{\max_i v_i}$

$\Rightarrow$ value($\text{OPT}^{\prime}$) $\geq , (1-\frac{\epsilon}{2})$ value(OPT)\
$\Rightarrow$ value($\text{OPT}^{\prime}$) $\geq , (\frac{1}{1 + \epsilon})$ value(OPT) ( $\because \textcolor{red}{1-\frac{\epsilon}{2} \geq \frac{1}{1+\epsilon}}$ )

Improvement version

上題的 $b = \frac{\epsilon}{2n}\tilde{V}$ 可以想成離散化 $v$ 值的刻度大小，我們可否在保持( $1 + \epsilon$ ) - approx. ratio 的前提下，跳大格一點( $b$ 取大一點)。從上式的推導可以發現，若想保持 approx. ratio ，$\tilde{V}$ 必須小於 value(OPT)，而想降低 running 的 order ， $\tilde{V}$ 需要跟 $v^{\star}$ 差不多 order 。也就是我們需要估計一個比 value(OPT) 小，但不會差太多的 $\tilde{V}$ , $\tilde{V} = \Theta(v^{\star})$。 (而且估計的 running time 不能高於之後 derive 出來的複雜度)

Greedy Algorithm to estimate $\tilde{V}$

Poly-time Approximation Scheme (PTAS)

Given $\epsilon > 0$, can find ($1 + \epsilon$)-approx. algorithm w/ running time is poly. for constant $\frac{1}{\epsilon}$

Fully Poly-time Approximation Scheme (FPTAS)

Given $\epsilon > 0$, can find ($1 + \epsilon$)-approx. algorithm w/ running time is poly. for constant $\frac{1}{\epsilon}$ and $n$ \
e.g 剛剛提到的 Rounded DP-based Algorithm

Psuedo-Poly Implementation

• $\Theta(n , v^{\star})$

• $\Theta(n , W)$ ，Online Judge

視題目所給的測資範圍，選擇running time 較小的實做方式。

• Share on Facebook
   
• Tweet
   
• Share on Google+
   
• Post to Tumblr
   
• Pin it
   
• Submit to Reddit