0-1背包问题-分支限界法(优先队列分支限界法)_01背包优先队列式分界法

问题描述

• 给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为c。
• 应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
• 在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。
  
  

算法的思想

• 首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。
• 在实现时，由Bound计算当前结点处的上界。在解空间树的当前扩展结点处，仅当要进入右子树时才计算右子树的上界Bound，以判断是否将右子树剪。进入左子树时不需要计算上界，因为其上界与其父节点上界相同。
• 在优先队列分支限界法中，结点的优先级定义为：以结点的价值上界作为优先级（由bound函数计算出）

步骤

1. 算法首先根据基于可行结点相应的子树最大价值上界优先级，从堆中选择一个节点（根节点）作为当前可扩展结点。
2. 检查当前扩展结点的左儿子结点的可行性。
3. 如果左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。
4. 当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界函数约束时,才将它加入子集树和活结点优先队列。
5. 当扩展到叶节点时，算法结束，叶子节点对应的解即为问题的最优值。

样例

 假设有4个物品，其重量分别为(4, 7, 5, 3)，价值分别为(40, 42, 25, 12)，背包容量W=10。将给定物品按单位重量价值从大到小排序，结果如下：

上界计算
   先装入物品1，剩余的背包容量为6，只能装入物品2的6/7(即42*(6/7)=36)。 即上界为40+6*6=76

已第一个up为例:40+6*(10-4)=76
打x的部分因为up值已经小于等于bestp了，所以没必要继续递归了。

分析演示

核心代码

• Typew c： 背包容量
• C： 背包容量
• Typew *w： 物品重量数组
• Typew *p： 物品价值数组
• Typew cw：当前重量
• Typew cp：当前价值
• Typep bestcp：当前最优价值

上界函数

template<class Typew, class Typep>
Typep Knap<Typew, Typep>::Bound(int i)
{// 计算上界
   Typew cleft = c - cw;  // 剩余容量
   Typep b = cp;
   // 以剩余物品单位重量价值递减序装入物品
   while (i <= n && w[i] <= cleft) {
      cleft -= w[i];
      b += p[i];
      i++;
      }
   // 装满背包
   if (i <= n) b += p[i]/w[i] * cleft;
   return b;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

0-1背包问题优先队列分支限界搜索算法

完整代码

#include <bits/stdc++.h>
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];
void InPut()
{
    scanf("%d %d", &n, &c);
    for(int i = 1; i <= n; ++i)
    {
     scanf("%d %d", &obj[i].price, &obj[i].weight);
     obj[i].id = i;
     obj[i].d = 1.0 * obj[i].price / obj[i].weight;
    }
 
    sort(obj + 1, obj + n + 1, compare);
//    for(int i = 1; i <= n; ++i)
//        cout << obj[i].d << " ";
//    cout << endl << "InPut Complete" << endl;
}
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);
//    cout << "加入点的信息为 " << endl;
//    cout << "p->lev = " << p->lev << " p->upprofit = " << p->upprofit << " p->weight =  " << p->weight << " p->profit =  " << p->profit << endl;
}
void MaxKnapsack()
{
    priority_queue<MaxHeapQNode *, vector<MaxHeapQNode *>, cmp > q; // 大顶堆
    MaxHeapQNode *E = NULL;
    cw = cp = bestp = 0;
    int i = 1;
    int up = Bound(1); //Bound(i)函数计算的是i还未处理时候的上限值
    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); //注意这里 up != up - obj[i].price而且 up >= up - obj[i].price
        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;
    }
}
void OutPut()
{
    printf("最优装入量为 %d\n", bestp);
    printf("装入的物品为 \n");
    for(int i = 1; i <= n; ++i)
        if(bestx[i] == 1)
          printf("%d ", i);
}
int main()
{
    InPut();
    MaxKnapsack();
    OutPut();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

测试样例

输入
4 10
40 4
42 7
25 5
12 3

输出
最优装入量为 65
装入的物品为
1 3