0/1背包问题 - 分枝定界优先队列

[复制链接]

字体大小: 正常放大

佛自业障

100 主题	17 听众	7535 积分

升级 50.7%

TA的每日心情

	开心 2018-6-4 15:01

签到天数: 7 天

[LV.3]偶尔看看II

群组: 2018年大象老师国赛优

群组: 高考备战

群组: 2018中小学数学建模冬

电梯直达

1^#

发表于 2018-10-31 09:14 |只看该作者 |正序浏览

|招呼Ta 关注Ta

0/1背包问题 - 分枝定界优先队列

flyfish

分枝定界branch and bound 分支定界法分枝界限法
不同的资料不同的叫法都是 branch and bound
在使用branch and bound 方法解背包问题时需要使用优先队列

优先队列使用标准库提供的std::priority_queue

一简单使用
#include "stdafx.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>       // std::priority_queue
#include <functional>
int _tmain(int argc, _TCHAR* argv[])
{
std::priority_queue<int> q;

q.push(90);
q.push(100);
q.push(70);
q.push(80);

while (!q.empty())
{
      std::cout << ' ' << q.top();
      q.pop();
}
std::cout << '\n';
}
输出是 100 90 80 70 自动按照由大到小输出

二由小到大输出则是下面代码
#include "stdafx.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>       // std::priority_queue
#include <functional>

int _tmain(int argc, _TCHAR* argv[])
{
std::priority_queue<int, std::vector<int>, std::greater<int> > q;

q.push(90);
q.push(100);
q.push(70);
q.push(80);
while (!q.empty())
{
      std::cout << q.top() << std::endl;
      q.pop();
}
return 0;
}

std::greater改成std::less由大到小输出

三自定义类型的比较

class Node
{
public:

int weight;
int value;
double bound;

public:
Node(int w, int v, double b) : weight(w), value(v),bound(b){}
bool operator ()(const Node & n1, const Node & n2)
{
      if (n1.bound < n2.bound) return true;

      if (n1.bound > n2.bound)
         return false;
      else
      return false;//strict weak ordering  条款21: 永远让比较函数对相等的值返回false
}

Node()
{

      weight = 0;
      value = 0;
      bound = 0.0;
}

};
int _tmain(int argc, _TCHAR* argv[])
{
std::priority_queue <Node, std::vector <Node>, Node > q;

      Node root(1, 7, 5.0);
      Node branch(3, 6, 7.0);
      Node leaf(5, 8, 6.0);

      q.push(root);
      q.push(branch);
      q.push(leaf);

      while (!q.empty())
      {
         std::cout << ' ' << q.top().value;
         q.pop();
      }
      std::cout << '\n';

return 0;
}
按照bound排序输出6,8 7

zan