亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

基本算法-0/1背包問題

系統 1626 0

? 關于0/1背包問題網上有非常多的博文,在此我謹記錄一下自己的理解。

? 問題表述:有N件物品和一個容量為V的背包。第i件物品的體積是C[i](0<=i<=N-1),價值是W[i]。求解將哪些物品裝入背包可使價值總和最大。每個物品最多只可以放入背包一次。

? 這個問題的經典解法思路如下:

? 我們用f[i][j]表示在考慮前i個物品時體積為j的背包的最大價值,注意,我們并不是把前i個物品全部放入背包,而是考慮i個物品中挑選一些放入背包,使得價值最大的那些情況。

? 首先,我們考慮只有1個物品(第0個)時,容量分別為0,1,...,V的各背包所包含物品的最大價值。很明顯,容量大于等于C[0]的背包的最大價值為W[0],容量小于C[0]的背包的最大價值為0。

? 然后,我們考慮再來一個(第i個)物品時,容量分別為0,1,...,V的各背包所包含物品的最大價值。對于某個背包,我們有兩種選擇:將該物品放入該背包或者不放入。

? 當我們將該物品放入某個體積為j的背包時,該背包的最大價值為f[i][j-C[i]]+W[i]。當我們不把該物品放入某個體積為j的背包時,該背包的最大價值為f[i-1][j]。所以在考慮前i個物品時,體積為j的背包的最大價值為f[i][j]=max{f[i-1][j],f[i][j-C[i]]+W[i]}.

? 迭代以上步驟,從i=0到N-1,最后得到的f[N-1][V]就是最后的答案。

? 上述算法的時間復雜度為O(VN),空間復雜度也是O(VN)。時間復雜度是最優的,而空間復雜度可以進一步優化:我們注意到在公式f[i][j]=max{f[i-1][j],f[i][j-C[i]]+W[i]}中,對于j從0到V,f[i][j]只與f[i-1][j]有關,而與i-2,i-3等情況下的f無關,所以我們只需要考慮前一次迭代(亦即i-1)的結果就可以。亦即f[j]=max{f[j],f[j-C[i]]+W[i]}.又因為在計算f[j]時用到了比j小的f:f[j-C[i]],所以在對j進行迭代時應該從后向前迭代:?

?

      
        1
      
      
        for
      
      (
      
        int
      
       i=0;i<N;i++
      
        ){

      
      
        2
      
      
        for
      
      (
      
        int
      
       j=V;j>=0;j--
      
        ){

      
      
        3
      
      
        if
      
      (j-item[i][0]>=0){
      
        //
      
      
        此處判斷是為了防止將j物品放入容量小于C[j]的背包中
      
      
        4
      
                           f[j]=max(f[j],f[j-item[i][0]]+item[i][1
      
        ]);

      
      
        5
      
      
                        }

      
      
        6
      
      
                    }           

      
      
        7
      
               }
    

? 我們可以用一個例子來展示一下上述代碼迭代的過程。取V=10,N=3.三個物品的體積分別為3,4,5.價值分別為4,5,6,迭代過程中f數組的值為:

? 0 0 0 4 4 4 4 4 4 4 4
? 0 0 0 4 5 5 5 9 9 9 9
? 0 0 0 4 5 6 6 9 10 11 11

? 第一行為只考慮第1個物品的情況。所有容量大于等于3的背包的價值都為該物品的價值:4.

? 第二行為只考慮前2個物品的情況。所有容量大于等于7的背包可以同時容納前2個物品,價值為4+5=9,容量為4-6的背包可以容納第2個物品,價值為5,容量為3的背包可以容納第1個物品,價值為4.

? 第三行以此類推。

? 我們取最后1行的最后一個數字為結果,亦即考慮所有3個物品的體積為10的背包的最大價值,為11.

參考文獻:

? [1] 0/1問題 動態規劃法

? [2] 背包問題九講 第一講 0/1背包問題

? [3] 背包之0/1背包 完全背包 多重背包詳解

?

基本算法-0/1背包問題


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 国产成人综合洲欧美在线 | 国产精品亚洲精品久久成人 | 九九热播 | 日韩经典欧美精品一区 | 9久re在线观看视频精品 | 欧美高清在线精品一区二区不卡 | 男人的天堂免费视频 | 久久乱码精品区中文字幕 | 久青草影院在线观看国产 | 国产伦精品一区二区三区在线观看 | 国产亚洲精品资源一区 | 水浒传删减剧情在线观看 | 日本xxxxx18护士xxx | 日本亚欧乱色视频在线网站 | 在线播放国产视频 | 精品久久中文网址 | 国产精品66在线观看 | 二性视频 | 久草视频大全 | 四虎影院永久免费观看 | 国产一区二区精品久久岳 | 欧美日韩视频一区二区 | 国产高清精品久久久久久久 | 日本xxxxxbbbbb精品| 在线中文字幕亚洲 | 国产成人一区二区 | 综合另类小说色区色噜噜 | 久久精品在线观看 | 天天操夜夜 | 日本不卡高清视频 | 变态 调教 视频 国产九色 | 狠狠色噜噜狠狠狠狠91 | 亚洲视频在线网站 | 美女被羞羞视频网站在线 | 伊人黄网 | 狠狠躁夜夜躁人人爽天天miya | 这里只有久久精品 | 高清性色生活片久久久 | 精品一区二区三区中文字幕 | 久久伊人热 | 日日做日日摸夜夜爽 |