问题描述

0-1背包问题

已知n个物品的价值vi和重量wi,背包的载重W,求能放入背包的最大价值。用分支限界方法解决此问题

问题分析

该背包是0-1背包,只有背包里的物品放与不放两种选择。在本题中,题目要求使用分支限界方法求解。故需要确定一下背包放物品的上界以及下界。

求上界:

即比背包放的实际最大价值要大。

计算方法:max(物品单位重量最大值) 背包容积

求下界:

在这里我们使用贪心算法,求得放入背包的物品价值最少不能低于该值

计算方法:优先选择价值高的物品放入,直到背包不能再放入任何其他物品

确定上下界以后,对背包每个物品分放与不放两种情况分析:

放:则要注意放入后的背包所剩体积(c – w )要大于零,否则不放。

若能放入,则有

w=w+goods.weight

v = v +goods.value

vb = v + (剩余没放的物品中物品单位重量最大值)剩余背包容量

vb用于时刻计算物品背包当前状态下到最后的最大价值

若vb值不小于由贪心算法求得的下界,则入队,否则不入队

不放:

则需要更新此时情况的最大上界

vb = v + (剩余没放的物品中物品单位重量最大值)剩余背包容量

若vb值不小于由贪心算法求得的下界,则入队,否则不入队

出口条件:

出队元素的w足够大,以至于不能放入任何物品

算法分析

首先从文件读取背包以及物品信息。所用时间T = O(n)

其次使用贪心算法求出物品下界,需要对物品按照价值做降序的快速排序,然后再使用一重循环,计算好下界。所用时间T = O(nlogn) + O(n) = O(nlogn)

之后使用优先队列,优先队列设置为大顶堆,每次弹出此时背包实际价值最大的元素出队,进行放与不放的操作。

由于优先队列用堆来实现,具有O(log n)时间复杂度的插入元素性能,O(n)的初始化构造的时间复杂度。插入与删除的时间复杂度为O(log n),构造二叉树的时间复杂度为O(n log n)

所以此步的时间复杂度大概为T =O(nlogn) +O(logn)约等于O(nlogn)*

最终该算法时间复杂度为T =O(n)+ O(nlogn) +O(nlogn)约等于O(nlogn)

分支限界的认识

  1. 以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树

  2. 分支限界法中,每一个活结点只有一次机会成为扩展结点,活结点一旦成为扩展结点,就一次性产生其所有儿子结点,其中导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中

  3. 然后从活结点表中取下一结点成为当前扩展结点

  4. 重复上述结点扩展过程,直至到找到所需的解或活结点表为空时为止

分支限界与回溯法区别

  1. 求解目标不同

    回溯法的求解目标是找出解空间树中满足约束条件的所有解

    分支限界法的求解目标则是尽快找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解

  2. 搜索方式不同

    回溯法以深度优先的方式(遍历结点)搜索解空间树

    分支限界法以广度优先或最小耗费优先的方式搜索解空间树

  3. 对扩展结点的扩展方式不同

    分支限界法中,每一个活结点只有一次机会成为扩展结点活结点一旦成 为扩展结点,就一次性产生其所有儿子结点

  4. 存储空间的要求不同

    分支限界法的存储空间比回溯法大得多,因此当内存容量有限时,回溯法成 功的可能性更大

参考代码

#include <bits/stdc++.h>
using namespace std;
typedef struct
{
double value = 0.00;
double weight = 0.00;
double pervalue = 0.00;
}goods;
//---------------------------
typedef struct{
double w = 0 ;
double v = 0;
double vb = 0;
int next = 0;
}point;
//-------------------------
bool operator<(point a, point b) {
return a.v > b.v;
}
//----------------------------
bool cmp(goods a , goods b){
if(a.pervalue == b.pervalue){
return a.weight < b.weight;
}
return a.pervalue > b.pervalue;
}
//-----------------------------

int main()
{
//file operate
char buffer[200];
ifstream in("0-1pacage.txt");
int number = 0 , c = 0 ;
in.getline(buffer,20);
sscanf(buffer,"%d%d",&number,&c);

vector<goods> v(number+1) ;
for(int i = 1 ; i < v.size() ; ++i){
double value = 0 , weight = 0 ;
in.getline(buffer,20);
sscanf(buffer,"%lf%lf",&weight,&value);
v[i].value = value;
v[i].weight = weight;
v[i].pervalue = v[i].value/v[i].weight;
}
sort(v.begin()+1,v.end(),cmp);
//max
int max = 0 ;
max = v[1].pervalue*c;
//min
int min = 0 ,tmp = 0 ;
for(int i = 1 ; i <= v.size() ; ++i){
if(tmp + v[i].weight <= c){
tmp += v[i].weight;
min += v[i].value;
}
else {break;}
}
//main
priority_queue<point> q;
point init;
init.w = 0 ,init.v = 0,init.vb = max , init.next = 1;
q.push(init);
double value = 0 ;
while(!q.empty()){
point m = q.top();
q.pop();
if(value < m.v) {value = m.v;}
{
// cout << m.v <<" "<< m.vb<<" "<<m.w<<" "<<m.next<<endl;
}
if(m.next != number+1){
//不加
double s = m.v + (c - m.w)*v[m.next+1].pervalue;
if(s >= min) {
point add;
add.w = m.w; add.v = m.v ; add.vb = s; add.next = m.next + 1 ;
q.push(add);
}
//加
//判断是否可以加
if(m.w + v[m.next].weight <= c){
point add;
add.w = m.w + v[m.next].weight;
add.v = m.v + v[m.next].value;
add.next = m.next + 1 ;
add.vb = add.v + (c - add.w)*v[add.next].pervalue;
if(add.vb < min) {continue;}
q.push(add);
}
}
}
cout << value;
return 0;
}

谢谢访问