01背包,動態(tài)規(guī)劃之0-1背包問題

            抖帥宮 972 2023-09-04

            01背包,動態(tài)規(guī)劃之0-1背包問題-第1張-觀點-玄機派

            來源頭條作者:小夸大夸在前面文章的例子里面講解了許多動態(tài)規(guī)劃的問題,說明了哪些問題可以用動態(tài)規(guī)劃來解決以降低時間復(fù)雜度。動態(tài)規(guī)劃里有許多經(jīng)典的問題,其中0-1背包問題是最基礎(chǔ)的問題,下面將進行講解什么是0-1背包問題及其講解。

            一、0-1背包問題關(guān)于背包問題,可以參考如下:

            根據(jù)維基百科,背包問題(Knapsack problem)是一種組合優(yōu)化的NP完全(NP-Complete,NPC)問題。

            問題可以描述為:給定一組物品,每種物品都有自己的重量和價格,在限定的總重量內(nèi),我們?nèi)绾芜x擇,才能使得物品的總價格最高。

            NPC問題是沒有多項式時間復(fù)雜度的解法的,但是利用動態(tài)規(guī)劃,我們可以以偽多項式時間復(fù)雜度求解背包問題。一般來講,背包問題有以下幾種分類:

            1、01背包問題

            2、完全背包問題

            3、多重背包問題

            其中最簡單的背包問題為01背包問題,下面為維基百科里的一張圖:

            怎么把價值為4美元12kg,價值為2美元2kg,價值為1美元1kg,價值為10美元4kg,價值為2美元1kg的物品進入只有15kg的背包,使其價值最大。

            問題可以描述為:

            1、問題描述

            01背包問題(01 knapsack problem):一共有n件物品,第i件物品的重量為w[i],價值為v[i]。在總重量不超過背包承載上限C的情況下,能夠裝入背包的最大價值是多少?

            如果用暴力解法

            2、背包問題用貪心算法無法解決例如,下圖,如果有id為:0,1,2的3個物品,其重量weight[]為:1,2,3,其價值value[]為:6,10,12。通過公式v/w,得到其價值為:6,5,4,要放入到空間為5的背包里。如果先放價值高的,就是放id為0,重量為1,價值為6的;再放id為1,重量為2,價值為10的。這時占用的重量就為1+2=3,還剩下5-3=2的重量,所以此時已經(jīng)不能再放id為0的物品。所以總的價值就是6+10=16。如下圖所示

            然而,我們明顯知道真正的最優(yōu)方法為如下的方式,放id為1和id為2的物品,其重量為5,價值可以達到10+12=22。

            因此解決背包這種問題貪心算法是不適用的,還是要用到動態(tài)規(guī)劃來解決。

            二、狀態(tài)定義與狀態(tài)轉(zhuǎn)移方程的確定由上一篇文章我們得知要解決動態(tài)規(guī)劃問題就是要定義好記憶化搜索數(shù)組和函數(shù)及函數(shù)的實現(xiàn)。我們先實現(xiàn)一下其代碼過程,后面再分析代碼實現(xiàn)具體的過程。

            1、記憶化搜索數(shù)組的定義memo[i,j]表示在前i件(包括i件)物品中選擇若干件放在承重為 j 的背包中,可以取得的最大價值。

            2、狀態(tài)定義與狀態(tài)轉(zhuǎn)移方程狀態(tài)定義(要求的結(jié)果):F(n,C) 考慮將n個物品放進容量為C的背包,使得價值最大。本文的值就為memo[n - 1][C]

            狀態(tài)轉(zhuǎn)移方程:F(i,c) 考慮將前i個物品放進容量為c的背包,得到的最大價值

            i和c的含義:表示為考慮將前i個物品放進容量為c的背包

            3、問題化解為求2個問題的最大值這時要求解的問題可以化解為求下面2個問題的最大值

            (1)第i個物品不放進背包里,這時的價值就是i-1時的價值:F(i-1,c)

            (2)如果第i個可以放入來,且不超過容量C,這是的價值為第i個物品的價值加上前面i-1的價值,注意這時i-1的重量為c-w(i):v(i)+F(i-1, c-w(i) )

            即問題變?yōu)榍蠼猓?)和(2)的最大值就可以。如下:

            千言萬語還不如直接看代碼來得實際。下面看2種方式的實現(xiàn)。

            4、記憶化搜索實現(xiàn)在看代碼之前大家記得看上面記憶化搜索數(shù)組的定義,狀態(tài)定義與狀態(tài)轉(zhuǎn)移方程。不要一頭鉆進代碼里,要先理解函數(shù)定義。

            private int[][] memo; 是一個二維數(shù)組,表示在前i件(包括i件)物品中選擇若干件物品放在承重為 j 的背包中,可以取得的最大價值。

            /// 背包問題 /// 記憶化搜索 /// 時間復(fù)雜度: O(n * C) 其中n為物品個數(shù); C為背包容積 /// 空間復(fù)雜度: O(n * C) public class Solution1 { private int[][] memo; public int knapsack01(int[] w, int[] v, int C){ if(w == null || v == null || w.length != v.length) throw new IllegalArgumentException("Invalid w or v"); if(C< 0) throw new IllegalArgumentException("C must be greater or equal to zero."); int n = w.length; if(n == 0 || C == 0) return 0; memo = new int[n][C + 1]; // 初始化數(shù)組 for(int i = 0; i< n; i ++) for(int j = 0; j<= C; j ++) memo[i][j] = -1; // 根據(jù)上面=》狀態(tài)定義(要求的結(jié)果):F(n,C)?考慮將n個物品放進容量為C的背包,使得價值最大。 // 要求的問題就是最后一個n-1, 容量為C return bestValue(w, v, n - 1, C); } // 用 [0...index]的物品,填充容積為c的背包的最大價值 private int bestValue(int[] w, int[] v, int index, int c){ if(c<= 0 || index< 0) return 0; if(memo[index][c] != -1) return memo[index][c]; int res = bestValue(w, v, index-1, c); if(c >= w[index]) res = Math.max(res, v[index] + bestValue(w, v, index - 1, c - w[index])); return memo[index][c] = res; } public static void main(String[] args) { } }5、動態(tài)規(guī)劃實現(xiàn)動態(tài)規(guī)劃的實現(xiàn)是自底向上實現(xiàn),和記憶化的方向是相反的,但其記憶數(shù)組的定義是一樣的。

            /// 背包問題 /// 動態(tài)規(guī)劃 /// 時間復(fù)雜度: O(n * C) 其中n為物品個數(shù); C為背包容積 /// 空間復(fù)雜度: O(n * C) public class Solution2 { public int knapsack01(int[] w, int[] v, int C){ if(w == null || v == null || w.length != v.length) throw new IllegalArgumentException("Invalid w or v"); if(C< 0) throw new IllegalArgumentException("C must be greater or equal to zero."); int n = w.length; if(n == 0 || C == 0) return 0; int[][] memo = new int[n][C + 1]; for(int j = 0 ; j<= C ; j ++) memo[0][j] = (j >= w[0] ? v[0] : 0 ); for(int i = 1 ; i< n ; i ++) for(int j = 0 ; j<= C ; j ++){ memo[i][j] = memo[i-1][j]; if(j >= w[i]) memo[i][j] = Math.max(memo[i][j], v[i] + memo[i - 1][j - w[i]]); } return memo[n - 1][C]; } public static void main(String[] args) { } }三、示例分析用上面的例子演示整個過程的示例分析:

            3個物品,容量為5。其id為:0,1,2的3個物品,其重量weight[]為:1,2,3,其價值value[]為:6,10,12;放入到空間為5的背包里。

            下面表格的藍色行0,1,2,3,4,5表示容量數(shù)量的變化從0到5;藍色列0,1,2為3個物品。表格表達的含義為:0,1,2的3個物品,其容量從0變化到5,各個情況的最大價值。

            表格里的數(shù)值表示為價值,表示在前i件(包括i件)物品中選擇若干件放在承重為 j 的背包中,可以取得的最大價值。

            1、剛開始都為空

            2、把id為0的物品放到表格里,在容量遞增時的各個價值如下。容量為0時價值都是為0,容量為1時價值為6,因為物品id為0的重量就是1,所以無論容量怎么遞增其價值都是為6

            3、當id為1的物品放入去時,因為它的重量為2,所以當容量為1時,它是不能放進去的,此時價值最大的依然為上一次的物品的價值,即為6

            4、當id為1的物品放入去時,當其容量到達為2時,這時物品id為1的就可以放進去了,但是根據(jù)v(i)+F(i-1, c-w(i) ),c-w(i) =》2-2=0 ,即id為0的物品就不能放到背包里了,此時的價值為10

            5、繼續(xù)往后走我們看當容量增加到3時,可以放下id為0和id為1的物品,這時物品的價值為它們的和10+6=16,符合v(i)+F(i-1, c-w(i) ),c-w(i) ,比原來的6大,所以此時為16

            增加到4,原理一樣

            6、當物品id變化為2,到達容量為3的時候,因為物品還是放不進去,還是前一個狀態(tài)id為0和id為1的2個物品,價值為16

            7、當物品id為2,其容量到達4的時候,這時可以放進去了,根據(jù)v(i)+F(i-1, c-w(i) ),12+6與16比較大小,取18

            8、到達最后一個的時候,容量達到了5,取的為10+12=22

            上一篇:hp咱的追求不偉大,MacBook
            下一篇:生辰八字怎么算五行 怎么算自己八字五行呀
            相關(guān)文章

             發(fā)表評論

            暫時沒有評論,來搶沙發(fā)吧~

            返回頂部小火箭
            亚洲aⅴ无码专区在线观看 | 亚洲色最新高清av网站| 亚洲AV日韩AV永久无码下载| 亚洲综合国产一区二区三区| 亚洲精品天堂成人片?V在线播放| 无码色偷偷亚洲国内自拍| 免费亚洲视频在线观看| 深夜国产福利99亚洲视频| 亚洲国产免费综合| 国产成人亚洲影院在线观看| 久久久久国产亚洲AV麻豆| 在线观看亚洲天天一三视| 亚洲中文字幕第一页在线 | 亚洲精品福利你懂| 亚洲色偷偷偷综合网| 亚洲私人无码综合久久网| 亚洲丶国产丶欧美一区二区三区| 亚洲高清一区二区三区电影| 日韩亚洲国产二区| 国产成人精品久久亚洲| 亚洲精品自在在线观看| 久久亚洲国产精品| 亚洲自偷自拍另类图片二区| 亚洲一区二区三区播放在线| 亚洲综合av一区二区三区不卡| 亚洲国产精品无码久久久秋霞1| 最新亚洲人成无码网站| 亚洲国产精品日韩| 国产亚洲色婷婷久久99精品| 无码专区—VA亚洲V天堂| 亚洲色图黄色小说| 97se亚洲国产综合自在线| 亚洲AV成人精品一区二区三区| 亚洲欧洲日产国码高潮αv| 亚洲日韩精品A∨片无码| 亚洲综合精品香蕉久久网97| 亚洲免费福利视频| 亚洲AV无码国产剧情| 久久亚洲2019中文字幕| 久久久久亚洲精品成人网小说| 亚洲福利电影一区二区?|