用動态規劃來優化0-1背包問題

用廣度優先搜和動态規劃來優化0-1背包問題

對于0-1背包問題一般采用貪心算法來解決，這裡使用廣度優先搜尋列舉所有情況，并将每次層次周遊的結果集進行優化删除不必要的集合，達到程式時間上的整體優化。

算法思路

每次加到結果集的數進行一次篩選，選出重量大于等于結果集中其他的數且價值大于等于它的數，删除選出來的數；

問題描述

五件商品重量和價值分别是：{2,6,},{2,3,},{6,5},{5,4},{4,6}。背包最大容納重量是10，求背包所能裝的最大值的物品。

注意：每個物品隻能裝一次。

代碼

筆者采用C++在 QT 環境下編譯代碼如下：

注意：由于有些老舊平台不支援C++ 11新的标準庫，此代碼的main函數下的數組初始化在vc6.0 等舊平台下編譯不通，如遇編譯不通請換個較新的編譯器（支援C++11标準），或者簡單修改下初始化方式，再編譯。

#include<iostream>
#include<string>
#include<vector>
using namespace std;
class goods{
public:
    int price;
    int weight;
    string track;// 記錄之前的軌迹
    goods(int w = ,int p = ,string t = "")
        :price( p ),weight( w ),track( t ){
        //構造函數
    }
};
goods operator+(const goods a,const goods b){
    goods c;
    c.price = a.price+b.price;
    c.weight = a.weight+b.weight;
    c.track = a.track +" + "+ b.track;
    return c;
}
template <class Type>
void bag0_1(const int n,const int c,const Type *gds)
{
    vector <Type> gdsres;//存結果集
    Type temp;
    int max =  , middle , j , x , i;
    gdsres.push_back(gds[]);
    max++;
    for(i=;i < n;i++){
        middle=max;
        for(j=;j < middle;j++){
            temp = gds[i];
            if(temp.weight <= c){
                gdsres.push_back(temp);
                max++;
            }
            temp = gdsres[j] + gds[i];
            if(temp.weight <= c){
                gdsres.push_back(temp);
                max++;
            }
        }
        for(j = middle;j < max ; j++ ){
            int count = ;
            temp = gdsres[j];
            for(int x = ;x < middle;x++){//檢查是否是更優的解
                if(gdsres[x].weight >= temp.weight && gdsres[x].price <= temp.price){
                    gdsres.erase(gdsres.begin()+x);
                    x--;
                    j--;
                    middle--;
                    max--;
                }
            }
            for(x = ;x < middle;x++){//檢查是否是更差的解
                if(gdsres[x].weight <= temp.weight && gdsres[x].price >= temp.price)
                    count = ;
            }
            if(!count){
                gdsres.erase(gdsres.begin() + j);
                j--;
                max--;
            }
        }
    }
    goods maxwet;
    for(i=;i< max;i++)
        if(gdsres[i].price>maxwet.price)
            maxwet=gdsres[i];
    cout<<maxwet.weight;
    cout<<" "<<maxwet.price<<endl;
    cout<<maxwet.track.c_str()<<endl;
}
int main(){
    goods gds[]={{,,"2 6"},
                  {,,"2 3"},
                  {,,"6 5"},
                  {,,"5 4"},
                  {,,"4 6"}};//初始化資料
    int n=,c=;
    bag0_1(n,c,gds);
    return ;
}
           

運作結果

8 15

2 6 + 2 3 + 4 6

程式思路

初始時gdsres裡面隻有{(2 6)}一組資料

第二次周遊會産生{(2 6)(2 3)(4 9)}三組資料由于(2 3)相較于(2 6)重量相同，但價值更高，這裡把(2 3)從結果集中删除。

按此規律依次是

第三次周遊{(2 6)(4 9)(8 11)(10 14)}

第四次{(2 6)(4 9)(8 11)(10 14)(7 10)(9 13)}

第五次{(2 6)(4 9)(6 12)(8 15)}

最後價值最大的(8 15)就是要求的結果了。

總結

這種方式設計算法在物品種類較很小的時候時間複雜度不會有所優化，相反不使用此算法時間更快。但當物品種類很大之後時間上的優化就會非常明顯。這對解決大資料問題很有幫助。