fenzhixianjie.txt

0/1背包问题的优先队列式分支限界算法程序

// 0-1 背包问题
// 优先队列式分支限界搜索
#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 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("\t 容量=%d \t 价值=%d 重量=%d \t 价值=%d 重量=%d\n", c,
            ansv1, answ1, ansv2, c - answ2);
        if (ansv1 != ansv2) getchar(); // 价值不等，等待
        if (answ1 != (c - answ2)) putchar(7); // 重量不等，响铃（方法不一样，存在不等）
    }
    
    return 0;
}