??前面的話??

本篇文章將介紹動態(tài)規(guī)劃中的背包問題——完全背包問題，前面我們已經(jīng)介紹了0-1背包問題，其實完全背包問題就只改了0-1背包問題的一個條件，即物品可選擇次數(shù)由一次改為無數(shù)次，僅此而已，下面我們就來開始介紹完全背包問題。

??博客主頁：未見花聞的博客主頁
??歡迎關(guān)注??點(diǎn)贊??收藏??留言??
??本文由未見花聞原創(chuàng)！
??首發(fā)時間：??2022年10月22日??
??堅持和努力一定能換來詩與遠(yuǎn)方！
??推薦書籍：??《算法》，??《算法導(dǎo)論》
??參考在線編程網(wǎng)站：???？途W(wǎng)??力扣
博主的碼云gitee，平常博主寫的程序代碼都在里面。
博主的github，平常博主寫的程序代碼都在里面。
??作者水平很有限，如果發(fā)現(xiàn)錯誤，一定要及時告知作者哦！感謝感謝！

??【問題導(dǎo)入】完全背包原題??

??題目詳情

有 $N$ 種物品和一個容量為 $C$ 的背包，每種物品都有無限件。

第 $i$ 件物品的體積是 $v[i]$ ，價值是 $w[i]$ 。

求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過背包容量，且價值總和最大。

其實就是在 0-1 背包問題的基礎(chǔ)上，增加了每件物品可以選擇多次的特點(diǎn)（在容量允許的情況下）。

示例 ：

輸入: N = 2, C = 5, v = [1,2], w = [1,2]
輸出: 5
解釋: 選一件物品 1，再選兩件物品 2，可使價值最大。

??解題思路與代碼

??樸素解法

我們可以直接將0-1背包的狀態(tài)定義直接拿來使用：

狀態(tài)定義： 不妨定義$f[i][j]$表示從前$i$件物品中選擇，容量不超過$j$的最大價值。

確定初始狀態(tài)： 當(dāng)只有一種物品選擇時，由于數(shù)量是無限的，所以盡量地選就行，不要超過容量$j$，不妨設(shè)選這一種物品的最大件數(shù)為$k$，則有$f[0][j]=k\times w[i],其中k\times v[i]<=j$。

狀態(tài)轉(zhuǎn)移方程推導(dǎo)： 當(dāng)我們選擇第$i$件物品的時候，我們可以選擇$0,1,\mathrm{2...}k$件，其中$k$是最大能夠選擇的件數(shù)，即在不超過容量$j$的情況下。

當(dāng)我們不選擇第$i$件物品時，即$k=0$，$f[i][j]=f[i?1][j]$。
當(dāng)我們選擇$1$第$i$件物品時，即$k=1$，$f[i][j]=f[i?1][j?v[i]]+w[i]$。
當(dāng)我們選擇$2$第$i$件物品時，即$k=2$，$f[i][j]=f[i?1][j?2?v[i]]+2?w[i]$。
…
當(dāng)我們選擇$k$第$i$件物品時，即$k=k$，$f[i][j]=f[i?1][j?k?v[i]]+k?w[i]$。

我們所要求的是最大的價值，所以取以上所有情況的最大值即可。

綜上所述，我們的狀態(tài)轉(zhuǎn)移方程就出來了，不妨記當(dāng)前物品的價值為：

$$f[i][j]=max(f[i?1][j?k?v[i]]+k?w[i]),k=0,1,...$$

實現(xiàn)代碼：

    /**
     *
     * @param n 物品個數(shù)
     * @param c 背包的總?cè)萘?     * @param w 每種物品的價值
     * @param v 每種物品的容量
     * @return 能將物品放進(jìn)背包的最大價值
     */
    public int cknapsack1(int n, int c, int[] w, int[] v) {
        //狀態(tài)定義f[i][j]表示最大價值
        int[][] f = new int[n][c + 1];
        //確定初始狀態(tài)
        for (int j = 1; j <= c; j++) {
            int k = j / v[0];
            f[0][j] = k * w[0];
        }
        //狀態(tài)轉(zhuǎn)移f[i][j]=max(f[i-1][j - k * v[i]]+k*w[i]
        for (int i = 1; i < n; i++) {
            int val = w[i];
            for (int j = 1; j <= c; j++) {
                int cur = 0;
                for (int k = 0; j >= k * v[i]; k++) {
                    int t = f[i - 1][j - k * v[i]] + k * val;
                    cur = Math.max(t, cur);
                }
                f[i][j] = cur;
            }
        }
        return f[n - 1][c];
    }

時間復(fù)雜度：$O(n?c?k)$，$k$的值不會大于$c$，因為最低物品價值為$1$，最多選擇的件數(shù)不會超過$c$。
空間復(fù)雜度：$O(n?c)$

??滾動數(shù)組優(yōu)化空間

根據(jù)觀察我們知道第$i$行的狀態(tài)僅依賴與第$i?1$行的狀態(tài)，因此我們可以使用滾動數(shù)組進(jìn)行優(yōu)化。

實現(xiàn)代碼：

    /**
     *
     * @param n 物品個數(shù)
     * @param c 背包的總?cè)萘?     * @param w 每種物品的價值
     * @param v 每種物品的容量
     * @return 能將物品放進(jìn)背包的最大價值
     */
    public int cknapsack2(int n, int c, int[] w, int[] v) {
        //狀態(tài)定義f[i][j]表示最大價值 滾動數(shù)組優(yōu)化
        int[][] f = new int[2][c + 1];
        //確定初始狀態(tài)
        for (int j = 1; j <= c; j++) {
            int k = j / v[0];
            f[0][j] = k * w[0];
        }
        //狀態(tài)轉(zhuǎn)移f[i][j]=max(f[i-1][j - k * v[i]]+k*w[i]
        for (int i = 1; i < n; i++) {
            int val = w[i];
            int ci = i & 1;
            int pi = (i - 1) & 1;
            for (int j = 1; j <= c; j++) {
                int cur = 0;
                for (int k = 0; j >= k * v[i]; k++) {
                    int t = f[pi][j - k * v[i]] + k * val;
                    cur = Math.max(t, cur);
                }
                f[ci][j] = cur;
            }
        }
        return f[(n - 1) & 1][c];
    }

對于時空復(fù)雜度，只是優(yōu)化了空間而已，所以時間復(fù)雜度不發(fā)生改變，空間復(fù)雜度優(yōu)化到$O(c)$。
時間復(fù)雜度：$O(n?c?k)$，$k$的值不會大于$c$，因為最低物品價值為$1$，最多選擇的件數(shù)不會超過$c$。
空間復(fù)雜度：$O(c)$

??一維數(shù)組優(yōu)化空間

首先我們對狀態(tài)轉(zhuǎn)移方程進(jìn)行一個簡單的推導(dǎo)：

$$f[i][j]=max(f[i?1][j],f[i?1][j?v[i]]+w[i],f[i?1][j?2?v[i]]+2?w[i],...,f[i?1][j?k?v[i]]+k?w[i])$$

$$f[i][j?v[i]]=max(f[i?1][j?v[i]],f[i?1][j?2?v[i]]+w[i],f[i?1][j?3?v[i]]+2?w[i]...,f[i?1][j?k?v[i]]+(k?1)?w[i])$$

其中$k?v[i]<=j$。

通過觀察上面兩個狀態(tài)的式子，我們發(fā)現(xiàn)后面一部分式子是差了一個$w[i]$如下圖：

所以我們可以進(jìn)一步優(yōu)化狀態(tài)轉(zhuǎn)移方程，即：

$$f[i][j]=max(f[i?1][j],f[i][j?v[i]]+w[i])$$

對于新推導(dǎo)出來的狀態(tài)轉(zhuǎn)移方程，它的狀態(tài)轉(zhuǎn)移僅僅只依賴與上一行同列狀態(tài)與同一行元素前面的元素，所以我們可以將原來的二維數(shù)組優(yōu)化為一維，由于它只依賴左邊與正上方的元素，我們可以采取從小到大遍歷背包容量狀態(tài)來求背包中所放物品最大值。

只保留【背包容量】維度，狀態(tài)轉(zhuǎn)移方程為：

$$f[j]=max(f[j],f[j?v[i]]+w[i])$$

實現(xiàn)代碼：

    /**
     *
     * @param n 物品個數(shù)
     * @param c 背包的總?cè)萘?     * @param w 每種物品的價值
     * @param v 每種物品的容量
     * @return 能將物品放進(jìn)背包的最大價值
     */
    public int cknapsack3(int n, int c, int[] w, int[] v) {
        //狀態(tài)定義f[i][j]表示最大價值 一維數(shù)組優(yōu)化
        int[] f = new int[c + 1];
        //確定初始狀態(tài)f[0]=0
        //狀態(tài)轉(zhuǎn)移
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= c; j++) {
                //不選擇物品
                int nopt = f[j];
                //選擇物品
                int opt = j >= v[i] ? f[j - v[i]] + w[i] : nopt;

                f[j] = Math.max(opt, nopt);
            }
        }
        return f[c];
    }

時間復(fù)雜度：$O(n?c)$
空間復(fù)雜度：$O(c+1)$

??總結(jié)

以上我們介紹了【完全背包問題】的樸素解法和優(yōu)化方案，其中一維優(yōu)化是最復(fù)雜的，因為使用了一些數(shù)學(xué)上的推導(dǎo)，比較抽象，不是特別容易理解，我建議自己嘗試推導(dǎo)一遍，這樣能夠更快的理解并且更深刻。
相比于0-1背包問題的優(yōu)化，形式上，我們只需要將 01 背包問題的「一維空間優(yōu)化」解法中的「容量維度」遍歷方向從「從大到小 改為 從小到大」就可以解決完全背包問題。
但本質(zhì)是因為兩者進(jìn)行狀態(tài)轉(zhuǎn)移時依賴了不同的格子：
0 -1 背包依賴的是「上一行正上方的格子」和「上一行左邊的格子」。
完全背包依賴的是「上一行正上方的格子」和「本行左邊的格子」。

文章來源地址http://www.zghlxwxcb.cn/news/detail-420853.html

到了這里，關(guān)于【動態(tài)規(guī)劃之完全背包問題】完全背包問題的通用解法與優(yōu)化的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！