目錄

前言&背包問題的歷史

?01背包

?1、題目

2、暴力解01背包

?Ⅰ、代碼

3、動態(tài)規(guī)劃解01背包

Ⅰ、二維dp數(shù)組解01背包

1）dp數(shù)組的含義

?2）遞推公式

?3）dp數(shù)組的初始化

?4）遍歷順序的討論

?5、代碼

?Ⅱ、一維數(shù)組解01背包

?1）一維數(shù)組|滾動數(shù)組

?2）一維數(shù)組的含義及遞推公式

?3）一維數(shù)組的初始化

?4）遍歷一維數(shù)組

5）遍歷順序的討論

?6）代碼

?完全背包

1、題目

?2、思路

?3、遍歷順序的討論

?4、代碼

題目推薦

前言&背包問題的歷史

背包問題(Knapsack problem)是一種組合優(yōu)化的NP完全問題（NP完全問題，是世界七大數(shù)學難題之一。 NP的英文全稱是Non-deterministic Polynomial的問題，即多項式復雜程度的非確定性問題。簡單的寫法是 NP=P？，問題就在這個問號上，到底是NP等于P，還是NP不等于P）。

背包問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內(nèi)，我們?nèi)绾芜x擇，才能使得物品的總價格最高。問題的名稱來源于如何選擇最合適的物品放置于給定背包中。

相似問題經(jīng)常出現(xiàn)在商業(yè)、組合數(shù)學，計算復雜性理、密碼學和應(yīng)用數(shù)學等領(lǐng)域中。也可以將背包問題描述為決定性問題，即在總重量不超過W的前提下，總價值是否能達到V？它是在1978年由Merkle和Hellman提出的。

背包問題已經(jīng)研究了一個多世紀，早期的作品可追溯到1897年???數(shù)學家托比亞斯·丹齊格（Tobias Dantzig，1884-1956）的早期作品??，并指的是包裝你最有價值或有用的物品而不會超載你的行李的常見問題。

?具體可看背包問題_百度百科 (baidu.com)

可以看到上面的圖，背包問題還是很有很多種,但其實我們非競賽人員只需要學會01背包、完全背包，最多再加上點多重背包。博主只討論01背包和完全背包問題。

我們都知道背包問題是動態(tài)規(guī)劃經(jīng)典問題，但為什么不可以使用貪心思維來解決呢？我舉個簡單例子。

?

?如果上面我們使用貪心思想總是去裝 價值 / 物品大小?大的，即最多裝價值為的16的物品，還剩余容量為3，無法再裝下其他物品，這也是為什么不能用貪心去做，無法最大化的利用背包空間。

?01背包

?1、題目

一共有N件物品，第i（i從1開始）件物品的重量為w[i]，價值為v[i]。在總重量不超過背包承載上限W的情況下，求能夠裝入背包的最大價值是多少？

2、暴力解01背包

?說起背包就會想到dp，使用動態(tài)規(guī)劃的方法寫，其實這也可以使用回溯算法暴力求解，大家不常用回溯算法暴力求解是因為每件物品都存在裝入和不裝入兩種情況，總的時間復雜度是O(2?)，?這是不可取的。但我們也可以了解了解怎么暴力求解背包問題。

還是使用以上面的例子試一試：

5 10
2 5 4 2 3
6 3 5 4 6

?Ⅰ、代碼

import java.util.Scanner;

public class Main {
    static int SetCapacity=0;//背包的初始容量
    static int MaxCapacity=0;//使用了背包多少容量
    static int MaxValue=0;//最大價值
    static void method(int[][] arr,int k,int capacity,int value){
        for (int i=k;i<arr.length;i++){
            if (SetCapacity-capacity>=arr[i][0]){//判斷當前背包的剩余容量是否可以裝下第i個物品
                capacity+=arr[i][0];
                value+=arr[i][1];
                method(arr,i+1,capacity,value);
                //回溯
                capacity-=arr[i][0];
                value-=arr[i][1];
            }else{//如果不行,則跳過第i個物品，繼續(xù)遞歸后面的物品，看是否可以裝下。
                if (capacity>=SetCapacity)//如果背包裝不下了，則退出循環(huán)，返回上一次遞歸
                    break;
                method(arr,i+1,capacity,value);
            }
        }
        if (value>MaxValue){
            MaxValue=value;
            MaxCapacity=capacity;
        }
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        SetCapacity=sc.nextInt();
        int[][] arr=new int[n][2];
        for (int i=0;i<n;i++){//物品大小
            arr[i][0]=sc.nextInt();
        }
        for (int i=0;i<n;i++){//物品價值
            arr[i][1]=sc.nextInt();
        }
        method(arr,0,0,0);
        System.out.println(MaxCapacity+" "+MaxValue);//9 17
    }
}

3、動態(tài)規(guī)劃解01背包

Ⅰ、二維dp數(shù)組解01背包

1）dp數(shù)組的含義

可能很多人會寫動態(tài)規(guī)劃的題目，會寫01背包，但是很多人卻不會去注重思考dp數(shù)組的含義，其代表著什么？

01背包的dp數(shù)組含義是：dp[i][j]?表示從下標為[0-i]的物品里任意取，放進容量為j的背包，價值總和最大是多少。

不懂可以看看下面圖，仔細想想。

?2）遞推公式

dp[i][j]=Max( dp[i-1][j] , dp[i-1][ j-w? ]+v??)

dp[i][j]我們在上面知道 這?表示從下標為[0-i]的物品里任意取，放進容量為j的背包，價值總和最大是多少。此時我們應(yīng)該考慮下標為i物品是否放入背包（先要考慮j-w?是否大于等于0，即此時是否能夠放入物品i?），于是就有兩種情況：放 或者 不放。

不放物品i就是dp[i-1][j]嘛，放物品i就是容量為j的背包需要留出這個物品i的容量才可以放物品i，即dp[i-1][ j-w? ],而這又是下標為 0到 i-1 的物品里任意取，放進容量為 j-w? 的背包，最大的價值總和。然后再由 dp[i-1][ j-w? ]+v???就是dp[i][j]放物品 i? 的最大價值。

然后 取 Max( dp[i-1][j] , dp[i-1][ j-w? ]+v??)??二者的最大值。

?3）dp數(shù)組的初始化

?我們由上面知道了求 dp[i][j] 需要知道?dp[i-1][j]和 dp[i-1][ j-w? ]+v??，即需要先知道上圖紅色箭頭所指的位置，這樣我們便清楚知道了，dp數(shù)組應(yīng)該如何初始化，即綠色箭頭所指的列和行。

初始化如下圖：

?dp數(shù)組初始化了，遞推公式我們也知道了，后面這個數(shù)組自然而然也可以求出來了。

?4）遍歷順序的討論

?上面我們得出dp數(shù)組是先遍歷物品，再遍歷背包容量，那可不可以先遍歷背包容量再遍歷物品，答案是可以的，但此時 dp[j][i] =Max( dp[ j-w? ][ i-1 ]+v? ,dp[ j ][ i-1 ] )。

而此時 dp數(shù)組的含義就是 容量為 j 的背包隨機放 0-i 之間的物品，所放物品的最大價值。

?

?5、代碼

?以先遍歷物品，在遍歷背包為例

public class Main {
    public static void main(String[] args) {
        int[] weight = {1,3,4};
        int[] value = {3,4,6};
        int bagSize = 4;
        method(weight,value,bagSize);
    }

    /**
     * 動態(tài)規(guī)劃獲得結(jié)果
     * @param weight  物品的重量
     * @param value   物品的價值
     * @param bagSize 背包的容量
     */
    public static void method(int[] weight, int[] value, int bagSize){

        // 創(chuàng)建dp數(shù)組
        int goods = weight.length;  // 獲取物品的數(shù)量
        int[][] dp = new int[goods][bagSize + 1];

        // 初始化dp數(shù)組
        // 創(chuàng)建數(shù)組后，其中默認的值就是0
        for (int j = weight[0]; j <= bagSize; j++) {
            dp[0][j] = value[0];
        }

        // 填充dp數(shù)組
        for (int i = 1; i < weight.length; i++) {
            for (int j = 1; j <= bagSize; j++) {
                if (j < weight[i]) {
                    /**
                     * 當前背包的容量都沒有當前物品i大的時候，是不放物品i的
                     * 那么前i-1個物品能放下的最大價值就是當前情況的最大價值
                     */
                    dp[i][j] = dp[i-1][j];
                } else {
                    /**
                     * 當前背包的容量可以放下物品i
                     * 那么此時分兩種情況：
                     *    1、不放物品i
                     *    2、放物品i
                     * 比較這兩種情況下，哪種背包中物品的最大價值最大
                     */
                    dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]);
                }
            }
        }

        // 打印dp數(shù)組
        for (int i = 0; i < goods; i++) {
            for (int j = 0; j <= bagSize; j++) {
                System.out.print(dp[i][j] + "\t");
            }
            System.out.println();
        }
    }
}

?輸出

0	3	3	3	3	
0	3	3	4	7	
0	3	3	4	7	

?Ⅱ、一維數(shù)組解01背包

?1）一維數(shù)組|滾動數(shù)組

?我們在上面知道了? 二維數(shù)組的遞推公式是?dp[i][j]=Max( dp[i-1][j] , dp[i-1][ j-w? ]+v??)。

即dp[i][j] 的值只與上一層的左上方和正上方有關(guān)。換句話說只與上一層有關(guān)。那我們是不是可以將二維dp數(shù)組降為一維dp數(shù)組呢？

答案是可以的。

我們可以發(fā)現(xiàn)如果把dp[i - 1]那一層拷貝到dp[i]上，表達式完全可以是：dp[i][j] = max(dp[i][j], dp[i][ j -w? ] +?v??);

與其把dp[i - 1]這一層拷貝到dp[i]上，不如只用一個一維數(shù)組了，只用dp[j]（一維數(shù)組，也可以理解是一個滾動數(shù)組）。

這就是滾動數(shù)組的由來，需要滿足的條件是上一層可以重復利用，直接拷貝到當前層。

?2）一維數(shù)組的含義及遞推公式

?而此時一維數(shù)組dp[j]的含義就是 ?容量為j的背包所背的最大價值。

那么如何推導dp[j]呢？

dp[j]可以通過dp[ j - w? ]推導出來，dp[j - w? ]表示容量為j - w? 的背包所背的最大價值。

dp[j - w? ] + v??表示 容量為 j - 物品i重量 的背包 加上 物品i的價值。（也就是容量為j的背包，放入物品i了之后的價值即：dp[j]）

此時dp[j]有兩個選擇，一個是不放物品i ，取自己 dp[j] 相當于 二維dp數(shù)組中的dp[i-1][j]，，一個是放物品i 取dp[j - w? ] + v?，然后求兩者最大值，所以遞歸公式為：

dp[j] = max(dp[j], dp[j - w?] + v?);

?3）一維數(shù)組的初始化

關(guān)于初始化，一定要和dp數(shù)組的定義吻合，否則到遞推公式的時候就會越來越亂。

dp[j]表示：容量為j的背包，所背的物品價值可以最大為dp[j]，那么dp[0]就應(yīng)該是0，因為背包容量為0所背的物品的最大價值就是0。

那么dp數(shù)組除了下標0的位置，初始化為0，其他下標應(yīng)該初始化多少呢？

看一下遞歸公式：dp[j] = max(dp[j], dp[j - w? ] + v??);

dp數(shù)組在推導的時候一定是取價值最大的數(shù)，如果題目給的價值都是正整數(shù)那么非0下標都初始化為0就可以了。

這樣才能讓dp數(shù)組在遞歸公式的過程中取到最大的價值，而不是被初始值覆蓋了。

?4）遍歷一維數(shù)組

?我們由上面知道了遞推公式為 dp[j] = max(dp[j], dp[j - w? ] + v??)。雖然它是一維數(shù)組，但和我們二維遞推數(shù)組還是很像的，所以想想我前面說的話：

dp[i][j] 的值只與上一層的左上方和正上方有關(guān)。

所以我們遍歷的時候 應(yīng)該先遍歷物品，再遍歷背包容量，并且背包是從大到小倒序遍歷。

 //遍歷順序：先遍歷物品，再遍歷背包容量
        for (int i = 0; i < wLen; i++){
            for (int j = bagWeight; j >= weight[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }

?還是這張圖，如果我們順序遍歷背包，那么后面的值就會被影響，這會導致物品i被重復多次加入。舉一個例子：物品1的重量 w?= 1，價值 v= 3

如果正序遍歷

dp[1] = dp[1 - w ] + v?= 3

dp[2] = dp[2 - w ] + v?= 6

此時dp[2]就已經(jīng)是6了，意味著物品1，被放入了兩次（這也違背了01背包每個物品只能放一次的規(guī)定，或者說這是完全背包），所以不能正序遍歷。

而從后往前循環(huán)，每次取的狀態(tài)不會和之前取的狀態(tài)重合，這樣每種物品就只取了一次。

5）遍歷順序的討論

那這個一維數(shù)組的兩個for循環(huán)是否可以顛倒呢？

答案是不可以的。

因為一維dp的寫法，背包容量一定是要倒序遍歷（原因上面已經(jīng)講了），如果遍歷背包容量放在上一層，那么每個dp[j]就只會放入一個物品，即：背包里只放入了一個符合當前容量的最大價值的物品。

倒序遍歷的原因是，本質(zhì)上還是一個對二維數(shù)組的遍歷，并且右下角的值依賴上一層左上角的值，因此需要保證左邊的值仍然是上一層的，從右向左覆蓋。

?可以看下面循環(huán)順序顛倒的代碼，發(fā)現(xiàn) 每個 dp[j]就只會放入一個物品

public class Main {
    public static void main(String[] args) {
        int[] weight = {1, 3, 4};
        int[] value = {3, 4, 6};
        int bagWight = 4;
        method(weight, value, bagWight);
    }

    public static void method(int[] weight, int[] value, int bagWeight){
        int wLen = weight.length;
        //定義dp數(shù)組：dp[j]表示背包容量為j時，能獲得的最大價值
        int[] dp = new int[bagWeight + 1];
        //遍歷順序：先遍歷背包容量,再遍歷物品，背包中就只會放一個物品
            for (int j =bagWeight; j >=0; j--){
                for (int i = 0; i < wLen&&j >= weight[i]; i++){
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        //打印dp數(shù)組
        for (int j = 0; j <= bagWeight; j++){
            System.out.print(dp[j] + " ");
        }
    }
}

?輸出

0 3 3 4 6 

?6）代碼

public class Main {
    public static void main(String[] args) {
        int[] weight = {1, 3, 4};
        int[] value = {3, 4, 6};
        int bagWight = 4;
        method(weight, value, bagWight);
    }

    public static void method(int[] weight, int[] value, int bagWeight){
        int wLen = weight.length;
        //定義dp數(shù)組：dp[j]表示背包容量為j時，能獲得的最大價值
        int[] dp = new int[bagWeight + 1];
        //遍歷順序：先遍歷物品，再遍歷背包容量
        for (int i = 0; i < wLen; i++){
            for (int j = bagWeight; j >= weight[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        //打印dp數(shù)組
        for (int j = 0; j <= bagWeight; j++){
            System.out.print(dp[j] + " ");//0 3 3 4 7
        }
    }
}

?完全背包

1、題目

有N種物品和一個容量為V的背包，每種物品都有無限件可用（這也是與01背包的區(qū)別）。

第i種物品的體積是c，價值是w。求解將哪些物品裝入背包可使這些物品的體積總和不超過背包容量，且價值總和最大。

?2、思路

這個問題非常類似于01背包問題，所不同的是每種物品有無限件，也就是從每種物品的角度考慮，與它相關(guān)的策略已并非取或不取兩種，而是有取0件、取1件、取2件……取[V/c]件等很多種（我們可以想象01背包就是取0件或者1件，所以完全背包其實就是01背包轉(zhuǎn)換過來的）。如果仍然按照解01背包時的思路，令f[v]表示前i種物品恰放入一個容量為v的背包的最大權(quán)值。仍然可以按照每種物品不同的策略寫出狀態(tài)轉(zhuǎn)移方程，像這樣：

dp[j]=Max（ dp[j] , dp[j-c]+w)??

?3、遍歷順序的討論

看了前面，我們知道01背包中二維dp數(shù)組的兩個for遍歷的先后循序是可以顛倒了，一維dp數(shù)組的兩個for循環(huán)先后循序一定是先遍歷物品，再遍歷背包容量，而且背包容量還要是倒序（因為順序的話就會將一個物品多次放入背包中）。

那么完全背包可以顛倒順序嗎？（指純完全背包）

答案是可以的。

上面我們說的因為順序的話就會將一個物品多次放入背包中，而完全背包每個物品有無限個，所以完全背包不需要倒序，順序即可。而01背包一維數(shù)組因為只能倒序，所以先遍歷背包容量，再遍歷背包，背包中就只會放一個物品。但是完全背包解決了順序倒序的問題，可以使用順序了，那它先先遍歷背包容量，再遍歷背包便也沒問題了。

?為了方便 理解，可以下面畫的兩個二維dp數(shù)組的圖

先物品后背包容量

?先背包容量再物品

?看了看到，不管怎么遍歷，都可以由前面的值得到正確的dp[i][j],不會受到影響

?4、代碼

public class Main {
    //先遍歷物品，再遍歷背包
    static void testCompletePack(){
        int[] weight = {1, 3, 4};
        int[] value = {3, 4, 6};
        int bagWeight = 4;
        int[] dp = new int[bagWeight + 1];
        for (int i = 0; i < weight.length; i++){ // 遍歷物品
            for (int j = weight[i]; j <= bagWeight; j++){ // 遍歷背包容量
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        for (int maxValue : dp){
            System.out.print(maxValue + " ");
        }
    }

    //先遍歷背包，再遍歷物品
    static void testCompletePackAnotherWay(){
        int[] weight = {1, 3, 4};
        int[] value = {3, 4, 6};
        int bagWeight = 4;
        int[] dp = new int[bagWeight + 1];
        for (int i = 1; i <= bagWeight; i++){ // 遍歷背包容量
            for (int j = 0; j < weight.length; j++){ // 遍歷物品
                if (i - weight[j] >= 0){
                    dp[i] = Math.max(dp[i], dp[i - weight[j]] + value[j]);
                }
            }
        }
        for (int maxValue : dp){
            System.out.print(maxValue + " ");
        }
    }
    public static void main(String[] args) {
       testCompletePack();//0 3 6 9 12 
        System.out.println();
       testCompletePackAnotherWay();//0 3 6 9 12 
    }
}

題目推薦

2. 01背包問題 - AcWing題庫

494. 目標和 - 力扣（Leetcode）

3. 完全背包問題 - AcWing題庫

?518. 零錢兌換 II - 力扣（Leetcode）

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

到了這里，關(guān)于背包問題——01背包|完全背包的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！