0/1背包问题 - 分枝定界 优先队列
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
页:
[1]