背包問題
先從栗子出發(fā)，你是一個有理想的吃貨柔滔，你的肚子只能容納500g 的食物泡徙，為了保證你得到的價值（營養(yǎng)）最大化，有以下幾份食物可以選擇
| 食物 | 質(zhì)量/weight （100g） | 價值/value（10g） |
|---|---|---|
| 米飯 | 2 | 4 |
| 黃瓜 | 1 | 5 |
| 西紅柿 | 1 | 8 |
| 牛肉 | 3 | 10 |
動動吃貨的小腦筋葛假，就知道，營養(yǎng)價值最大化的選擇是
牛肉+黃瓜+西紅柿 共 23（10g）營養(yǎng)滋恬！
可是該怎么使用程序計(jì)算出答案呢聊训？
思路
肚子的資源有限，對每一種食物有兩種選擇：吃或者不吃夷恍。
判斷的依據(jù)有兩點(diǎn)：
（1）肚子能否裝得下食物魔眨？
（2）吃他的價值，是否比不吃他的價值大酿雪？大則吃下遏暴，不大則不吃。
假設(shè)d（i指黎，w）表示肚子剩w（g）時朋凉，有 i 樣食物可供選擇，我們能得到的最大價值醋安。i 表示第 i 樣食物杂彭。我們需要求的是d（4墓毒，5）
根據(jù)上面的邏輯（1）
如果肚子裝不下，因?yàn)槭澄飅沒裝進(jìn)去亲怠，那么d(i,w) = d(i-1,w)
肚子裝得下所计，那我需要判斷 [不放] d(i-1,w) 和 [放] d(i-1,w-w[i])+v[i] 誰大。
結(jié)合上面兩條規(guī)律团秽，我們得到:
狀態(tài)轉(zhuǎn)移方程式
d(i, w)=max{ d(i-1, w), d(i-1,w-w[i]) + v[i] }
我們給每樣食物加上序號
假如我們考慮吃或不吃從下向上按照序號順序 4主胧，3，2习勤，1
d（4踪栋，5）表示只有牛肉、西紅柿图毕、黃瓜夷都、米飯可以選擇時，能得到的最大價值予颤。如果我知道d（3囤官，5）和d（3，2）荣瑟，我就能得到d（4治拿，5）
d(4 , 5)=max{ d(3,5) , d(3,5-3) }=max{ d(3,5) , d(3,2) + 10}
d（4摩泪，5）表示只有西紅柿笆焰、黃瓜、米飯可以選擇時见坑，能得到的最大價值嚷掠。如果我知道d（2，5）和d（2荞驴，4）不皆，我就能得到d（3，5）
d(3 , 5)=max{d(2,5) , d(2,4)}
按照上面的往下分解,最終都會指向d(0,w)～邏輯如下圖：
d(0,w)代表選 0 件物品的放入背包容量為 w 的背包的最大價值熊楼，所以為 0霹娄。d(i,0)代表選 i 件物品放入背包容量為 0 的背包的最大價值，也為 0鲫骗。
將樹圖的d值繼續(xù)整理得到最優(yōu)價值表
var value = [5, 8, 4, 10],
size = [1, 1, 2, 3],
d = [],
n = 4,
C = 5;
//初始化數(shù)組
for (var k = 0; k <= n; ++k) {
d[k] = [];
}
for (var i = 0; i <= n; ++i) {
for (var w = 0; w <= C; ++w) {
d[i][w] = (i == 0) ? 0 : d[i - 1][w];
if (i > 0 && w >= size[i - 1])
d[i][w] = Math.max(d[i - 1][w], d[i - 1][w - size[i - 1]] + value[i - 1]);
}
}
console.log(d[4][5])//23
總結(jié)
01背包問題的這種解法讓我感受到了遞歸的強(qiáng)大犬耻，將大問題轉(zhuǎn)換成小問題，然后得到小問題的答案向上求解执泰！
2. 例題
鏈接：https://www.nowcoder.com/questionTerminal/9ba85699e2824bc29166c92561da77fa
來源：耪泶牛客網(wǎng)
一種雙核CPU的兩個核能夠同時的處理任務(wù)，現(xiàn)在有n個已知數(shù)據(jù)量的任務(wù)需要交給CPU處理术吝，假設(shè)已知CPU的每個核1秒可以處理1kb计济，每個核同時只能處理一項(xiàng)任務(wù)茸苇。n個任務(wù)可以按照任意順序放入CPU進(jìn)行處理，現(xiàn)在需要設(shè)計(jì)一個方案讓CPU處理完這批任務(wù)所需的時間最少沦寂，求這個最小的時間学密。
3. 資料
動態(tài)規(guī)劃之01背包問題--表格思路來源
