0-1背包问题（分支限界法）_分支限界法0-1背包问题

0.问题描述

给定一背包的容量C，和n个物品的重量wi价值vi，求在背包容量允许的条件下能装入的最大价值

1.问题分析

①解空间：子集树，第i层每个节点有两棵子树：选择物品i，不选择物品i

②优先队列的优先级如何确定？

每个节点的祖先节点都已经确定，那么可以得到已经装入背包的物品的价值，加上剩余 物品能装入背包的最大价值，依此得到优先级，即当前结点的“值”。

这里用的是近似，剩余的物品按照单位重量价值非升序排序，将单位重量价值大的先放 入，放不下整个物品的话，就放入一部分。

③剪枝：进入左子节点时，物品的重量小于剩余背包的容量；进入右子结点时，要满足 上界约束。进入一个子结点就把它加入优先队列。

上界约束：当前结点的“值”比最优解的值要大。

2.输入数据

输入背包的容量，物品的重量和价值

3.输出数据

输出能装入背包的最大价值

4.测试样例设计

100 5
77 92
22 22
29 87
50 46
99 90
 
200 8
79 83
58 14
86 54
11 79
28 72
62 52
15 48
68 62
 
300 10
95 89
75 59
23 19
73 43
50 100
22 72
6 44
57 16
89 7
98 64
 

二、算法设计与分析

1.算法的基本思想

 

变成了非层次遍历

 

比如：

1. 第一层根结点，左右子结点都满足条件，加入队列；右结点优先级比较高
2. 处理根节点的右结点，它的左右子结点都可以加入，现在队列里面有它父结点的左子结点和它的两个子节点，其中它的左子结点优先级比较高
3. 处理根节点的右子结点的左子结点，两个子节点都可以加入……

基本思想：

①输入的物品重新排序，按照单位重量价值降序排序

②在一个优先队列里面保存目前待处理的结点，取出的队首元素是值最大的，目前最有 可能成为最优解路径的一部分。

③不断取出队首元素进行处理，考察其左右子结点，满足条件加入优先队列

④不断重复以上③步骤，直到处理的结点是叶子结点，那么它到根节点的路径一定是最 优解。

2.输入和输出的格式

从文件输入，输出到文件。

有多组输入，每组数据第一行是背包的容量C，和物品的件数n，接下来的n行第i行 是物品i的重量，物品i的价值。

3.算法的具体步骤

 

 

4.算法的时空分析

①空间复杂性：限界函数为O(1),最坏情况下需搜索2^(n +１) –２个节点，需O(2^n ) 个空间存储节点，则算法空间复杂性为O(2^n )。
②时间复杂性：限界函数时间复杂度为O(n),而最坏情况有2^(n +１) – ２个节点，若 对每个节点用限界函数判断，则其时间复杂度为O(n2^n).而算法中时间复杂度主要依赖 限界函数，则算法的时间复杂度为O(n2^n)。

四、测试结果

 

全部代码：

#include <bits/stdc++.h>
#include <fstream>
#include <iostream>
using namespace std;
class Object
{
public:
    int id;//编号 
    int weight;//重量 
    int price;//价值 
    float d;//单位重量价值 
};
class MaxHeapQNode
{
public:
    MaxHeapQNode *parent;//父结点，可以记录下路径 
    int lchild;//左子结点 
    int upprofit;//值 
    int profit;//当前价值 
    int weight;//重量 
    int lev;//层次 
};
//建立优先队列时使用的 
struct cmp
{
    bool operator()(MaxHeapQNode *&a, MaxHeapQNode *&b) const
    {
        return a->upprofit < b->upprofit;
    }
};
 
//用于预处理的重排 
bool compare(const Object &a, const Object &b)
{
    return a.d >= b.d;
}
 
int n;//物品件数 
int c;//背包容量 
int cw;//当前重量 
int cp;//当前解 
int bestp;//最优解的值 
Object obj[100];//物品集合 
int bestx[100];//最优解的物品集合 
ifstream in("input.txt");
ofstream out("output.txt");
 
//上界函数 
int Bound(int i)
{
    int tmp_cleft = c - cw;
    int tmp_cp = cp;
    while(tmp_cleft >= obj[i].weight && i <= n)
    {
        tmp_cleft -= obj[i].weight;
        tmp_cp += obj[i].price;
        i++;
    }
    if(i <= n)
    {
        tmp_cp += tmp_cleft * obj[i].d;
    }
    return tmp_cp;
}
 
//添加节点到优先队列 
void AddAliveNode(priority_queue<MaxHeapQNode *, vector<MaxHeapQNode *>, cmp> &q, MaxHeapQNode *E, int up, int wt, int curp, int i, int ch)
{
    MaxHeapQNode *p = new MaxHeapQNode;
    p->parent = E;
    p->lchild = ch;
    p->weight = wt;
    p->upprofit = up;
    p->profit = curp;
    p->lev = i + 1;
    q.push(p);
}
 
//分支限界法求解 
void MaxKnapsack()
{
	//运用了优先队列，里面存储结点的指针，建立在动态数组上，以cmp来确定优先级 
    priority_queue<MaxHeapQNode *, vector<MaxHeapQNode *>, cmp > q;  
    //初始化 
    MaxHeapQNode *E = NULL;
    cw = cp = bestp = 0;
    int i = 1;
    int up = Bound(1);
    //当处理的层次没有达到叶子结点，不断处理队列中的结点 
    while(i != n + 1)
    {
    	//左子结点，如果小于背包剩余容量，可以加入 
        int wt = cw + obj[i].weight; 
        if(wt <= c)
        {
            if(bestp < cp + obj[i].price)
                bestp = cp + obj[i].price;
            AddAliveNode(q, E, up, cw + obj[i].weight, cp + obj[i].price, i, 1);
        }
        
        //右子结点，如果可能产生最优解，可以加入 
        up = Bound(i + 1);
        if(up >= bestp) //（注意这里必须是大于等于） 
        {
            AddAliveNode(q, E, up, cw, cp, i, 0);
        }
        //取出队首结点给下一次循环来处理 
        E = q.top();
        q.pop();
        cw = E->weight;//（结点的重量） 
        cp = E->profit;//（结点的价值） 
        up = E->upprofit;//（结点的值） 
        i = E->lev;//（结点的层次） 
    }
    //构造最优解的物品集合 
    for(int j = n; j > 0; --j)
    {
        bestx[obj[E->lev-1].id] = E->lchild;
        E = E->parent;
    }
}
 
//输入&&预处理
int InPut()
{
	if(in>>c){
		in>>n; 
	    for(int i = 1; i <= n; ++i)
	    {
	        in>>obj[i].weight>>obj[i].price;
	    	obj[i].id = i;
	    	obj[i].d = 1.0 *obj[i].price / obj[i].weight;
	    }
	 	//重排 
	    sort(obj + 1, obj + n + 1, compare);
	    return 1;
	}
	return 0;
}
 
//输出 
void OutPut()
{
    out<<bestp<<'\n';
    for(int i = 1; i <= n; ++i)
        if(bestx[i] == 1)
           out<<i<<' ';
	out<<'\n'; 
}
 
int main()
{
    while(InPut()){
	    MaxKnapsack();
	    OutPut();
	}
	in.close();
	out.close();
    return 0;
}