VIVO筆試題——背包問題

背景：VIVO提前批筆試題遇到了01背包，就記得動态規劃動态規劃，記得表格法，突然失憶怎麼寫。

來自背包九講

01背包

有 N 件物品和一個容量為 V 的背包。放入第 i 件物品耗費的容量是 Ci，得到的

價值是 Wi。求解将哪些物品裝入背包（每個物品隻可放一件物品）可使價值總和最大（最優化問題）?

思路

自頂而下的方式去思考問題，設f（i，v）為選取前 i 件物品裝入容量為 v 的背包中的物品最大值；那麼f（i，v）等于不選 i 物品的 f 和選 i 物品(判斷容量範圍)的 f 的最大值。

即：

f(i,v) = max{f(i-1,v),f(i-1,v-Ci)+Wi}

思考問題用自頂而下的方式，但是編碼的話，若是自頂而下必然會出現“子問題的重疊”而導緻的時間複雜度的提高。

那麼就采用，自下而上的方式去編碼，既然

f(i,v) = max{f(i-1,v),f(i-1,v-Ci)+Wi}

，那麼就從f(0,v)、f(1,v)開始循環去計算，避免了重複的子問題的計算。

編碼

（1）初始化耗費容量和總容量(遞增)的二維dp數組，第0行第0列初始化為0；

（2）編寫狀态轉移方程，注意每一列是

從 Ci 到 V

或者

從1到V + 容量判斷

。

public static int dpCore1(int V, int[] cost, int[] value) {
        int N = cost.length;
        // 初始化數組表格
        int[][] dp = new int[N + 1][V + 1];
        // 前0個物品,全是0
        for (int i = 0; i < N + 1; i++) {
            dp[i][0] = 0;
        }
        // 沒有容量,全是0
        for (int i = 0; i < V + 1; i++) {
            dp[0][i] = 0;
        }
        for (int i = 1; i < N + 1; i++) {
            for (int j = cost[i-1]; j < V + 1; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - cost[i - 1]] + value[i - 1]);
            }
        }
        return dp[N][V];
    }
           

空間優化

思考，

f(i,v) = max{f(i-1,v),f(i-1,v-Ci)+Wi}

->

f(v) = max{f(v),f(v-Ci)+Wi}

用一個f[0…v]儲存目前價格最大值，那麼将第二個循環從V到Ci倒着來周遊，這樣就保證了在推f[v]的時候用的是上一輪計算的結果，即f[v-ci]儲存的狀态是上一輪計算的f(i-1,v-ci)（因為倒着來，較小的值還沒更新）

編碼

public static int dpCore2(int V, int[] cost, int[] value) {
        int N = cost.length;
        // 初始化dp一維數組
        int[] dp = new int[V + 1];
        for (int i = 1; i < N + 1; i++) {
            for (int j = V; j >= cost[i - 1]; j--) {
            	// 注意此處是倒着來的,j - cost[i - 1]此時是比j小的數字,由于是倒着來的,故還沒更新,儲存的内容是上一輪的
                dp[j] = Math.max(dp[j], dp[j - cost[i - 1]] + value[i - 1]);
            }
        }
        return dp[V];
    }
           

初始化問題

思想來自背包九講：若要求背包必須裝滿，那麼初始化dp數組時，除了dp[0]為0外其他的都為

負無窮

；若不要求裝滿，而是價值盡量大，那麼dp全部初始化為

。含義就是：若果必須裝滿，那麼隻有在容量為0且什麼都不裝的情況下才能滿足要求，容量＞0沒有合法解；若不要求裝滿，那在各個容量情況下都可以不放而為0。

完全背包問題

完全背包就是物品不止一個，可以拿多次。

題目：有 N 種物品和一個容量為 V 的背包，每種物品都有無限件可用。放入第 i 種物品的費用是 Ci，價值是 Wi。求解：将哪些物品裝入背包，可使這些物品的耗費的費用總和不超過背包容量，且價值總和最大。

思路1

類似01背包的思想，隻是每一步max中多個而不是2個的對比狀态，其轉移方程如下：

f(i,v) = max{f(i-1,v-k*Ci)+k*Wi | 0≤k*Ci≤v}

該方程的時間複雜度為

O(NV*∑(v/ci))

，其中

∑(v/ci)

是求解每一步

f(i,v)

所需要的時間複雜度。

優化

首先将大于 V 的物品去掉，在将費用相同價值最高的選出來，再将

Ci≤Cj && Wi≥Wj

的 j 物品直接去掉，在用上述方法進行計算。

思路2

轉換成01背包來求解，在給定 V 的條件下，将每一個物品拆分成

[V/Ci]

個物品，且拆分出來的物品的價值W為

k*Wi

，求解這個新的01背包問題。

更高效的轉換方法：把第 i 件物品拆分成費用為Ci2k，價值為Wi2k的若幹物品，其中

k

取遍滿足Ci2k的非負整數。思想在于，任何一個數字都可以用二進制數表示，即多個2k才表示。這樣每件物品拆分成O(log[V/Ci])件物品。

正統思路3

将01背包優化後的流程中的倒序周遊改成正序周遊。

for(int j = Ci ; i < V+1 ; j++)

之前倒序是為了f[v]是上次i-1時儲存的值，而正序是為了選過之後還可以選（小的已經選過，再次比較），選其中的最大值。

多重背包問題

不是無限可拿，而是最多Mi件可用，耗費Ci、價值Wi。

思路1

還是用類似于01背包的思路，轉移方程如下：

f(i,v) = max{f(i-1,v-k*Ci)+k*Wi | 0≤k*Ci≤v,0≤k≤Mi}

，時間複雜度

O(V*∑Mi*∑(v/ci))

。

思路2

還是拆分的思想，每件物品的花費和價值分别乘系數就是拆分後物品的屬性，對于給的Mi，可以拆分成1,2,22,23,Mi-2k+1的系數，且k是滿足Mi-2k+1>0的最大整數。若Mi=13，則可以分系數為1,2,4,6的4件物品。