1. 簡(jiǎn)介

背包問題是一個(gè)有很多應(yīng)用的組合優(yōu)化問題。在本Java教程中，動(dòng)力節(jié)點(diǎn)小編將用 Java 解決這個(gè)問題。

2. 背包問題

在背包問題中，我們有一組物品。每個(gè)項(xiàng)目都有一個(gè)重量和一個(gè)價(jià)值：

我們想把這些物品裝進(jìn)背包。但是，它有一個(gè)重量限制：

因此，我們需要選擇總重量不超過重量限制的物品，并且它們的總價(jià)值盡可能高。 例如，上面例子的最佳解決方案是選擇 5kg 的物品和 6kg 的物品，在重量限制內(nèi)，最大值為 40 美元。

背包問題有幾種變化。在本教程中，我們將關(guān)注0-1 背包問題。在 0-1 背包問題中，每個(gè)項(xiàng)目要么被選中，要么被拋在后面。我們不能拿走一個(gè)項(xiàng)目的部分金額。此外，我們不能多次拿走一個(gè)項(xiàng)目。

3. 數(shù)學(xué)定義

現(xiàn)在讓我們用數(shù)學(xué)符號(hào)形式化 0-1 背包問題。給定一組n 個(gè)項(xiàng)目和權(quán)重限制W，我們可以將優(yōu)化問題定義為：

這個(gè)問題是 NP 難的。因此，目前還沒有多項(xiàng)式時(shí)間算法來解決它。然而，有一個(gè)偽多項(xiàng)式時(shí)間算法使用動(dòng)態(tài)規(guī)劃來解決這個(gè)問題。

4. 遞歸解決方案

我們可以使用遞歸公式來解決這個(gè)問題：

在這個(gè)公式中，M(n,w)是重量限制為w的n 個(gè)項(xiàng)目的最優(yōu)解。它是以下兩個(gè)值中的最大值：

重量限制為w的(n-1)個(gè)項(xiàng)目的最優(yōu)解(不包括第n個(gè)項(xiàng)目)

第n項(xiàng)的值加上(n-1)項(xiàng)的最優(yōu)解和w減去第n項(xiàng)(包括第n項(xiàng))的權(quán)重

如果第n個(gè)項(xiàng)目的重量超過當(dāng)前重量限制，我們不包括它。因此，屬于上述兩種情況的第一類。

我們可以在 Java 中實(shí)現(xiàn)這個(gè)遞歸公式：

int knapsackRec(int[] w, int[] v, int n, int W) {
    if (n <= 0) { 
        return 0; 
    } else if (w[n - 1] > W) {
        return knapsackRec(w, v, n - 1, W);
    } else {
        return Math.max(knapsackRec(w, v, n - 1, W), v[n - 1] 
          + knapsackRec(w, v, n - 1, W - w[n - 1]));
    }
}

在每個(gè)遞歸步驟中，我們需要評(píng)估兩個(gè)次優(yōu)解決方案。因此，此遞歸解的運(yùn)行時(shí)間為O(2 n )。

5. 動(dòng)態(tài)規(guī)劃方案

動(dòng)態(tài)規(guī)劃是一種將其他呈指數(shù)級(jí)困難的規(guī)劃問題線性化的策略。這個(gè)想法是存儲(chǔ)子問題的結(jié)果，以便我們以后不必重新計(jì)算它們。

我們也可以用動(dòng)態(tài)規(guī)劃解決0-1背包問題。為了使用動(dòng)態(tài)規(guī)劃，我們首先創(chuàng)建一個(gè)維度從 0 到n和 0 到W的二維表。然后，我們使用自下而上的方法，用這張表計(jì)算最優(yōu)解：

int knapsackDP(int[] w, int[] v, int n, int W) {
    if (n <= 0 || W <= 0) {
        return 0;
    }
    int[][] m = new int[n + 1][W + 1];
    for (int j = 0; j <= W; j++) {
        m[0][j] = 0;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= W; j++) { 
            if (w[i - 1] > j) {
                m[i][j] = m[i - 1][j];
            } else {
                m[i][j] = Math.max(
                  m[i - 1][j], 
                  m[i - 1][j - w[i - 1]] + v[i - 1]);
            }
        }
    }
    return m[n][W];
}

在這個(gè)解決方案中，我們對(duì)項(xiàng)目編號(hào)n和重量限制W有一個(gè)嵌套循環(huán)。因此，它的運(yùn)行時(shí)間是O(nW)。

6. 結(jié)論

在本教程中，我們展示了 0-1 背包問題的數(shù)學(xué)定義。然后我們通過 Java 實(shí)現(xiàn)為這個(gè)問題提供了一個(gè)遞歸算法解決方案。最后，我們使用動(dòng)態(tài)規(guī)劃來解決這個(gè)問題。