0-1揹包問題還有它的衍生問題的解決思路

0-1 揹包問題

0-1揹包問題是經典的動態規劃問題，它有兩種衍生的問題形式，我們稱之為完全揹包問題和多重揹包問題

基本的0-1揹包問題：

熱動分析。jpg

給一個capacity為n的揹包，能裝weight總共不超過n的物品，給定m個物品，每一個物品具有價值value和重量weight，我們希望能裝的物品value的總和越大越好，那麼應該怎麼做呢？

#include

#include

#include

static

constexpr

int

MAX_N

=

SOME_VAL

（）；

static

constexpr

int

MAX_M

=

SOME_VAL

（）；

static

int

weight

［

MAX_M

］；

static

int

value

［

MAX_M

］；

static

int

dp_cache

［

MAX_M

］［

MAX_N

］；

static

int

n

，

m

；

// 初始化

static

inline

void

init

（）

{

for

（

int

i

=

0

；

i

<

MAX_M

；

++

i

）

memset

（

dp_cache

［

i

］，

0

，

sizeof

（

int

）

*

MAX_N

）；

memset

（

weight

，

0

，

sizeof

（

weight

））；

memset

（

value

，

0

，

sizeof

（

value

））；

}

// 獲取輸入

static

inline

void

get_input

（

std

：：

istream

&

is

=

std

：：

cin

，

std

：：

ostream

&

os

=

std

：：

cout

）

{

is

>>

n

>>

m

；

for

（

int

i

=

1

；

i

<=

m

and

i

<=

MAX_M

；

++

i

）

{

is

>>

weight

［

i

］

>>

value

［

i

］；

}

}

// 演算法執行

static

inline

int

proc

（）

{

for

（

int

i

=

1

；

i

<=

m

and

i

<=

MAX_M

；

++

i

）

{

for

（

int

j

=

1

；

j

<=

n

and

j

<=

MAX_N

；

++

j

）

{

if

（

weight

［

i

］

<=

j

）

dp_cache

［

i

］［

j

］

=

std

：：

max

（

dp_cache

［

i

-

1

］［

j

］，

dp_cache

［

i

-

1

］［

j

-

weight

［

i

］］

+

value

［

i

］）

else

dp_cache

［

i

］［

j

］

=

dp_cache

［

i

-

1

］［

j

］

}

}

return

dp_cache

［

m

］［

n

］；

}

int

main

（

int

argc

，

char

*

argv

［］）

{

init

（）；

get_input

（）；

std

：：

cout

<<

proc

（）

<<

std

：：

endl

；

return

0

；

}

以上這個程式碼基本就是解決基本0-1揹包問題的演算法思路了，我們可以看到，問題解決的關鍵在於找到一條合理的狀態轉移方程，所以我們考慮用一個合適的“容器”，用來記錄一些中間狀態，比如dp_cache［i］［j］用來表示：

考慮前i個物品（1，。。。，i）中，在容量為j的情況下能夠裝下的物品的最大價值。為了減少思維負擔，我們信任這個最大價值，並且認為他是最優的，那麼下一步的問題就是我們要不要在繼續裝下一個物品

那麼問題就轉化成dp_cache［i + 1］［j］究竟是容量不夠沒有裝下第 i+1 個物品，還是裝下了卻得不償失所以不裝，還是裝下了確實地能夠提高整體容納物品的價值總和，所以我們會有下面的思考

dp_cache［i + 1］［j］ = k

當不能裝下這個物品（第i + 1個物品），也就是j比第i + 1個物品的的重量要小，那麼自然而然不裝下第i + 1個物品，k就是dp_cache［i］［j］

當能夠裝下這個物品，那麼我們需要考慮要不要裝下它，是否值得

如果值得，那麼k就是dp_cache［i］［j - weight［i + 1］］ + value［i + 1］，也就是考慮前i個物品，在容量為j - weight［i+1］扣除第i+1個物品的剩餘容量的最佳值加上裝入的新物品的價值之和

否則，保持不變，也就是k = dp_cache［i］［j］比裝入這個物品後的情況（dp_cache［i］［j - weight［i + 1］］ + value［i + 1］）要大，那麼我們不裝入這個新的物品

為了方便下面我們使用dp陣列代指dp_cache

這裡注意一下

值得注意的是，我們在迭代的過程中，要求dp［i］［j］需要考慮的“原材料”，也就是我們所說的迭代前項，是dp［i-1］［0，1，2，。。。，j］與本行的資料都沒有關係（指dp［i］［0，1，2，3，。。。，j - 1］），僅僅只用到了上一行的資料，也就是說，將暫存陣列從二維最佳化為一維是可能的

| xx1 | xx2 | xx3 |

| oo1 | oo2 | tag |

如上表所示，要求tag，那麼xx是需要用到的，oo是用不到的，而要求第二行第二列的值，也只需要第一行第一列，第一行第二列的值作為推導的前項。

假如我們只用一個一維陣列dp_cache來暫存價值資訊，並且我們還只有第一行的資料

他現在長這樣

| xx1 | xx2 | xx3 |

現在，我們要求下一行第一個資料oo1，沒問題，直接使用這個一維陣列的第一個資料遞推

他現在長這樣

| oo1 | xx2 | xx3 |

接下來，我們要求下一個資料oo2，但是問題出現了，求oo2需要xx1還有xx2，但是xx1已經被覆蓋了，這樣的話我們這個想法就宣告失敗了。

那麼，如果我們倒著來求dp［i+1］［0。。。j］呢？

我們先求oo3（也就是之前的tag），oo3需要xx1， xx2， xx3來遞推得到，也確實有，所以我們順利得到oo3

這樣，這個表現在長這樣

| xx1 | xx2 | oo3 |

我們再求oo2，需要xx2和xx1，可以得到

| xx1 | oo2 | oo3 |

最後我們需要求oo1，可以由xx1推導得到

| oo1 | oo2 | oo3 |

這樣，我們前i + 1個物品的dp陣列已經求出來了

所以相對應的，我們可以把我們的演算法程式碼最佳化一下，注意由於dp_cache結構改變init（）函式也應當改變

// 新初始化函式

static

inline

void

init

（）

{

memset

（

dp_cache

，

0

，

sizeof

（

dp_cache

））；

memset

（

weight

，

0

，

sizeof

（

weight

））；

memset

（

value

，

0

，

sizeof

（

value

））；

}

這樣，第二個版本的演算法執行函式就出來了

// 第二個版本

// 將dp_cache［MAX_M］［MAX_N］改為dp_cache［MAX_N］

static

int

dp_cache

［

MAX_N

］；

static

inline

int

proc

（）

{

for

（

int

i

=

1

；

i

<=

m

and

i

<=

MAX_M

；

++

i

）

{

for

（

int

j

=

n

；

j

>=

0

and

j

<=

MAX_N

；

——

j

）

{

if

（

j

>=

weight

［

i

］）

dp_cache

［

j

］

=

std

：：

max

（

dp_cache

［

j

-

weight

［

i

］］

+

value

［

i

］，

dp_cache

［

j

］）；

}

}

return

dp_cache

［

n

］；

}

如果j小於weight［i］那麼，顯然是沒有繼續往下遍歷的必要了，所以可以繼續改為

// 最終版本

static

int

dp_cache

［

MAX_N

］；

static

inline

int

proc

（）

{

for

（

int

i

=

1

；

i

<=

m

and

i

<=

MAX_M

；

++

i

）

{

for

（

int

j

=

n

；

j

>=

weight

［

i

］

and

j

<=

MAX_N

；

——

j

）

dp_cache

［

j

］

=

std

：：

max

（

dp_cache

［

j

-

weight

［

i

］］

+

value

［

i

］，

dp_cache

［

j

］）；

}

return

dp_cache

［

n

］；

}

以上，就是0-1揹包問題的解法了，假設物品有m個，揹包容量為n，他的空間複雜度是O（n），時間複雜度是O（n*m）；

時間上應該是可以再最佳化的（比如說最後一次迭代不去求dp［m］［0。。。。j-1］，直接返回dp［m］［n］也就是dp_cache［n］），但是O（n*m）的時間複雜度還是逃不掉的

完全揹包問題

魔法分析。jpg

給一個capacity為n的揹包，能裝weight總共不超過n的物品，給定m種物品，每一種物品具有價值value和重量weight，我們希望能裝的物品value的總和越大越好，那麼應該怎麼做呢？

注意這個問題和基本0-1揹包問題的區別！！！

注意這個問題和基本0-1揹包問題的區別！！！

注意這個問題和基本0-1揹包問題的區別！！！

m種物品的數量是不限的！

m種物品的數量是不限的！

m種物品的數量是不限的！

有的小夥伴這個時候就有點懵逼了，那咋辦啊，暴力遍歷一下啊？

// 我們假設初始化函式沒有問題

static

int

dp_cache

［

MAX_M

］［

MAX_N

］；

static

inline

int

proc

（）

{

int

tmp_max

；

for

（

int

i

=

1

；

i

<=

MAX_M

and

i

<=

m

；

++

i

）

{

for

（

int

j

=

1

；

j

<=

MAX_N

and

j

<=

n

；

++

j

）

{

tmp_max

=

dp_cache

［

i

-

1

］［

j

］；

for

（

int

k

=

1

；

k

*

weight

［

i

］

<=

j

；

++

k

）

{

tmp_max

=

std

：：

max

（

tmp_max

，

dp_cache

［

i

-

1

］［

j

-

k

*

weight

［

i

］］

+

k

*

value

［

i

］）

}

dp_cache

［

i

］［

j

］

=

tmp_max

；

}

}

return

dp_cache

［

m

］［

n

］；

}

這種做法簡單粗暴夠直接，我喜歡，但是它沒有利用到同一行的資料

我們記

k1 = dp［i］［j］ + value［i］

k2 = dp［i - 1］［j + weight［i］］

dp［i］［j］代表的是前 i

種

物品在 j 這個容量下的最優值，我們足夠地信任他，那麼當我們考慮dp［i］［j + weight［i］］的值的時候，我們要作出一個判斷，是繼續裝第 i 種物品更加合適還是隻考慮前 i - 1 種但是容量增大更合適

也就是說

記 x = j + weight［i］

dp［i］［x］ = max（dp［i］［x - weight［j］］ + value［i］， dp［i - 1］［x］）

dp［i］［x］ = max（k1， k2）

這樣的話，我們就可以得到相對不那麼暴力的演算法了

// 第二版

// 我們假設初始化函式沒有問題

static

int

dp_cache

［

MAX_M

］［

MAX_N

］；

static

inline

int

proc

（）

{

for

（

int

i

=

1

；

i

<=

MAX_M

and

i

<=

m

；

++

i

）

{

for

（

int

j

=

1

；

j

<=

MAX_N

and

j

<=

n

；

++

j

）

{

if

（

j

<

weight

［

i

］）

dp_cache

［

i

］［

j

］

=

dp_cache

［

i

-

1

］［

j

］；

else

dp_cache

［

i

］［

j

］

=

std

：：

max

（

dp_cache

［

i

］［

j

-

weight

［

i

］］

+

value

［

i

］，

dp_cache

［

i

-

1

］［

j

］）；

}

}

return

dp_cache

［

m

］［

n

］

}

發現了沒有，dp[i][j]的遞推的“原材料”是dp[i][j-w]還有dp[i-1][j]

我們是否可以效仿之前提到的做法，最佳化這個演算法的空間複雜度，將二維暫存陣列轉化為一維陣列以節省空間呢

當然可以！！

由於之前詳細講過轉化成滾動陣列的驗證方法，這裡只是給出較為簡略的說明

這是二維陣列版本

| xx1 | xx2 | xx3 |

| oo1 | oo2 | oo1 |

好的，現在假設我們已經得到了前 i - 1 種的結果 xx1 xx2 xx3

| xx1 | xx2 | xx3 |

現在我們要求 oo1， oo1需要xx1還有邊界的0（希望這個無需說明）作為遞推的前項

現在這個表長這樣

| oo1 | xx2 | xx3 |

現在我們要求 oo2，oo2要求同一行的前置位已經求出和同一列的前置位已經求出，也就是ooX（X < 2）還有xx2的資料作為遞推的前項，這裡剛好滿足，所以我們填下oo2

現在這個表長這樣

| oo1 | oo2 | xx3 |

現在我們要求 oo3，oo3要求同一行的前置位已經求出和同一列的前置位已經求出，也就是ooX（X < 3）還有xx3的資料作為遞推的前項，這裡剛好滿足，所以我們填下oo3

現在這個表長這樣

| oo1 | oo2 | oo3 |

大功告成

我們反過來思考一下，為什麼基本的0-1揹包問題的遞推要避開同一行的資料而不得不倒著遍歷？

恰恰是因為要避免重複裝入第i個物品

而在完全揹包問題中，我們要反其道行之，就是要考慮可能的重複裝入情況，這樣最終的程式碼反而是非常簡潔的

// 最終版，初始化函式什麼的自己去改，這裡只展示proc函式

static

int

dp_cache

［

MAX_N

］；

static

inline

int

proc

（）

{

for

（

int

i

=

1

；

i

<=

m

and

i

<=

MAX_M

；

++

i

）

{

for

（

int

j

=

weight

［

i

］；

j

<=

n

and

j

<=

MAX_N

；

++

j

）

dp_cache

［

j

］

=

std

：：

max

（

dp_cache

［

j

-

weight

［

i

］］

+

value

［

i

］，

dp_cache

［

j

］）；

}

return

dp_cache

［

n

］；

}

程式碼僅供參考

多重揹包問題

不想分析。jpg

你直接把它轉換成基本0-1揹包問題不就完事了麼，這題摸了

結束

最後祝您，身體健康，再見