背包問題學(xué)習(xí)筆記

xiao7cn 發(fā)布于2019-08-20 18:05 / 2405人閱讀

摘要：狀態(tài)轉(zhuǎn)移方程背包問題的狀態(tài)轉(zhuǎn)移方程是其中即表示前件物品恰放入一個(gè)容量為的背包可以獲得的最大價(jià)值。求解將哪些物品裝入背包可使這些物品的體積總和不超過背包容量，且價(jià)值總和最大。

01背包 01背包的概念

有N件物品和一個(gè)容量為V的背包。第i件物品的費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使價(jià)值總和最大。
從這個(gè)題目中可以看出，01背包的特點(diǎn)就是：每種物品僅有一件，可以選擇放或不放。

狀態(tài)轉(zhuǎn)移方程

01背包問題的狀態(tài)轉(zhuǎn)移方程是:

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

其中,即fi表示前i件物品恰放入一個(gè)容量為v的背包可以獲得的最大價(jià)值。
上述方程右邊可以理解為兩種情況,取最優(yōu)值.
情況一:第i件不放進(jìn)去,這時(shí)所得價(jià)值為:fi-1;
情況二:第i件放進(jìn)去,這時(shí)所得價(jià)值為:fi-1]+w[i];

情況二的意思是,如果第i件放進(jìn)去,那么在容量V-c[i]里就要放進(jìn)前i-1件物品.(引用自)

案例解析

有編號分別為a,b,c,d,e的五件物品，它們的重量分別是2,2,6,5,4，它們的價(jià)值分別是6,3,5,4,6，現(xiàn)在給你個(gè)承重為10的背包，如何讓背包里裝入的物品具有最大的價(jià)值總和？

首先要明確這張表是至底向上，從左到右生成的.
只要你能通過找規(guī)律手工填寫出上面這張表就算理解了01背包的動態(tài)規(guī)劃算法。
為了敘述方便，用e2單元格表示e行2列的單元格，這個(gè)單元格的意義是用來表示只有物品e時(shí)，有個(gè)承重為2的背包，那么這個(gè)背包的最大價(jià)值是0，因?yàn)閑物品的重量是4，背包裝不了
對于d2單元格，表示只有物品e，d時(shí),承重為2的背包,所能裝入的最大價(jià)值，仍然是0，因?yàn)槲锲積,d都不是這個(gè)背包能裝的。(引用自)

編程實(shí)現(xiàn)

var n = 5; //物品數(shù)量,該參數(shù)可以自行設(shè)定
var v = 10; //背包體積,該參數(shù)可自行設(shè)定
var volumArray = [4, 3, 5, 2, 5];//物品體積組成的數(shù)組,該參數(shù)可自行設(shè)定
var valueArray = [9, 6, 1, 4, 1];//物品價(jià)值組成的數(shù)組,該參數(shù)可自行設(shè)定
var tempArray = [];

for (let a = 0; a < n; a++) {
    tempArray[a] = [];
    for (let b = 0; b < v; b++) {
        tempArray[a].push(0);
    }
}

for (let i = 0; i < n; i++) {
    for (let j = 0; j < v; j++) {
        tempArray[i][j] = i == 0 ? 0 : tempArray[i - 1][j];
        if (i > 0 && j >= volumArray[i - 1]) {
            tempArray[i][j] = tempArray[i][j] >= tempArray[i - 1][j - volumArray[i - 1]] + valueArray[i - 1] ? tempArray[i][j] : tempArray[i - 1][j - volumArray[i - 1]] + valueArray[i - 1];
        }
    }
}

console.log(tempArray[n - 1][v - 1]);

完全背包 完全背包的概念

有N種物品和一個(gè)容量為V的背包，每種物品都有無限件可用。
第i種物品的體積是c，價(jià)值是w。求解將哪些物品裝入背包可使這些物品的體積總和不超過背包容量，且價(jià)值總和最大。

狀態(tài)轉(zhuǎn)移方程

參考上述01背包的轉(zhuǎn)移方程,不難得出:

f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}

偽代碼實(shí)現(xiàn)如下:

for i=1...N
    for v=0...V
        for k=1...v/w[i]
            f[i][v] = max{f[i-1][v],f[i-1][v-k*w[i]]+k*c[i]};

案例解析

給你六種面額1,5,10,20,50,100元的紙幣,假設(shè)每種幣值的數(shù)量都足夠多,編寫程序求組成N元的不同組合個(gè)數(shù).

function fn (all) {
    const arr = [1, 5, 10, 20, 50, 100],
        len = arr.length,
        res = [];
    for (let i = 0; i <= len; i++) {
        res[i] = [];
        res[i][0] = 1;
    }
    for (let j = 1; j <= all; j++) {
        res[0][j] = 0;
    }
    for (let i = 1; i <= len; i++) {
        for (let j = 1; j <= all; j++) {
            res[i][j] = 0;
            for (let k = 0; k <= j / arr[i - 1]; k++) {
                res[i][j] += res[i - 1][j - k * arr[i - 1]];
            }
        }
    }
    return res[len][all];
}