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

0-1 背包问题・优先队列式分支限界搜索// 0-1 背包问题
// 优先队列式分支限界搜索
// http://kapinter.spaces.live.com 原创

#include <stdio.h>
#include <time.h>
#include <queue> // 用到里面的优先队列(priority_queue)
using namespace std;

const int N = 15;         // 物品数量
const int MAXW = 1000;    // 物品价值、重量上限
const int LEN = N * MAXW; // 背包容量上限
int v[N];                 // 价值数组
int w[N];                 // 重量数组
int x[N];                 // 解数组
int ansv1, answ1;
int ansv2, answ2;

struct node {
int upv;      // 结点价值上界
int cv;       // 结点价值
int cw;       // 结点重量
int level;    // 活结点层序号
bool LChild; // 左儿子标志
node *parent; // 父结点指针
node(int upv, int cv, int cw, int level, bool LChild, node *parent) :
upv(upv), cv(cv), cw(cw), level(level), LChild(LChild), parent(parent)
{ }
};

struct cmp { // 节点的优先级为当前结点继续扩展可能产生的最大价值
bool operator() (const node *&a, const node *&b) {
return (a->upv < b->upv);
}
};

priority_queue<node *, vector<node *>, cmp> p;

struct list {
list *next;
node *p;
list(list *next, node *p) : next(next), p(p)
{ }
} head(NULL, NULL);

void addListNode(node *p)
{
list *next = head.next;
head.next = new list(next, p);
}

void dropList()
{
list *next = head.next;
head.next = NULL;
while (next) {
delete (next->p);
list *last = next;
next = next->next;
delete (last);
}
}

node *addLiveNode(int upv, int cv, int cw, int level, bool LChild, node *parent)
{
node *e = new node(upv, cv, cw, level, LChild, parent);
p.push(e);
return e;
}

void getLiveNode(int &cv, int &cw, int &level, node *&parent)
{
node *e = p.top();
p.pop();
cv = e->cv;
cw = e->cw;
level = e->level;
parent = e;
}

void dropLive()
{
while (!p.empty()) p.pop();
}

int Bound(int i, int n, int cv, int cleft) // 上界函数
{
while (i<n && w[i]<=cleft) // n表示物品总数, cleft为剩余空间
{
cleft -= w[i];         // w[i]表示i所占空间
cv += v[i];            // v[i]表示i的价值
i++;
}
if (i < n)
cv += v[i] * cleft / w[i]; // 切割物品装满背包剩余容量

return cv;
}

void Knapsack(int c, int n, int x[])
{
int upv = Bound(0, n, 0, c); // (从?开始统计, n, 当前已有价值, 剩余重量)
int cv = 0;
int cw = 0;
bool LChild = false;
node *parent = NULL;
int bestv = 0;

// 第i层, 当扩展到叶节点时确定最优值
for (int i=0; i<n; getLiveNode(cv, cw, i, parent)) {
upv = Bound(i, n, cv, c – cw);
if (cw + w[i] <= c) // 左儿子可行
{
if (cv + v[i] > bestv) bestv = cv + v[i];
addListNode(addLiveNode(upv, cv + v[i], cw + w[i], i + 1, true, parent));
}
upv = Bound(i + 1, n, cv, c – cw);
if (upv >= bestv)
addListNode(addLiveNode(upv, cv, cw, i + 1, false, parent));
}

for (int j=n-1; j>=0; j–)
{
x[j] = parent->LChild;
parent = parent->parent;
}

dropLive();
dropList();
}

void Deep(int flo, int curv, int leftw) // (第?个, 已有价值, 剩余可装重量)
{
if (leftw < 0) return; // 剩余可装重量为负
int temp = curv;
for (int i=flo; i<N; i++) temp += v[i];
if (temp < ansv2) return; // 继续下去可能产生的最大价值小于已经产生的价值

if (flo == N) {
if (curv > ansv2 || curv == ansv2 && leftw > answ2)
{
ansv2 = curv;
answ2 = leftw;
}
}
else {
Deep(flo + 1, curv, leftw);
Deep(flo + 1, curv + v[flo], leftw – w[flo]);
}
}

void Swap(int &x, int &y)
{
int t = x;
x = y;
y = t;
}

void Sort(int v[], int w[], int n)
{
for (int i=0; i<n; i++)
for (int j=i+1; j<n; j++)
if (v[i] * w[j] < v[j] * w[i]) // 后面单位重量价值大
{
Swap(v[i], v[j]);
Swap(w[i], w[j]);
}
}

int main()
{
srand(time(0));
for (int i=0; i<N; i++)
{
v[i] = rand() % MAXW + 1;
w[i] = rand() % MAXW + 1;
}
Sort(v, w, N); // 依其单位重量价值从大到小进行排列

for (int c=0; c<=LEN; c++)
{
Knapsack(c, N, x);

ansv1 = answ1 = 0;
for (int i=0; i<N; i++)
{
answ1 += w[i] * x[i];
ansv1 += v[i] * x[i];
}
ansv2 = answ2 = -1;
Deep(0, 0, c); // (第?个, 已有价值, 剩余可装重量)

printf(” 容量=%d 价值=%d 重量=%d 价值=%d 重量=%d
“, c,
ansv1, answ1, ansv2, c – answ2);
if (ansv1 != ansv2) getchar(); // 价值不等,等待
if (answ1 != (c – answ2)) putchar(7); // 重量不等,响铃(方法不一样,存在不等)
}

return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>