用动态规划来优化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)就是要求的结果了。

总结

这种方式设计算法在物品种类较很小的时候时间复杂度不会有所优化，相反不使用此算法时间更快。但当物品种类很大之后时间上的优化就会非常明显。这对解决大数据问题很有帮助。