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

基本算法-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條評論
主站蜘蛛池模板: 精品动漫中文字幕一区二区三区 | 亚欧精品在线观看 | 国产美女一级毛片 | 夜夜夜夜夜夜夜猛噜噜噜噜噜噜 | 日韩中文字幕一区二区不卡 | 五月天婷婷缴情五月免费观看 | 久久久一区二区三区不卡 | 色老头在线观看精品 | www.夜夜| 久久青青草原精品国产麻豆 | 99久久免费国产精精品 | 国产精品午夜高清在线观看 | 成人激情视频在线 | 波多野结衣绝顶大高潮 | 成人私人影院在线观看网址 | h视频在线观看免费网站 | 番茄视频在线观看黄版本免费 | 在线视频亚洲一区 | 国产亚洲精品自在线观看 | 国产精品一区二区国产 | 国产中文字幕在线免费观看 | 中文字幕亚洲一区二区va在线 | 99久久99久久免费精品蜜桃 | 成人午夜啪啪免费网站 | 国内精品久久久久久久星辰影视 | 五月情视频在线观看 | 九九久久久久久久爱 | 国产91成人精品亚洲精品 | 亚洲图区综合 | 欧美国产成人一区二区三区 | 欧美国产成人一区二区三区 | 性夜黄a爽爽免费视频国产 性夜影院爽黄a爽免费看网站 | 亚洲a免费 | 99精品欧美 | 天天操天天干天天操 | 国产综合色在线视频区 | 欧美毛片aaaaa片久久久久 | 天天射天天射天天射 | 久久精品国产清自在天天线 | 久久这里只有精品国产 | 四虎成人精品国产一区a |