knapsack01_branchbound.c

《算法和数据结构——C语言描述》

/* 0/1背包问题的分支定界法算法*/


#include<stdio.h>
#include<stdlib.h>

#define  MAXNUM   100

struct node{
    int step;
    double price;
    double weight;
    double max, min;
    unsigned long po;
};

typedef struct node DataType;
struct  SeqQueue {		/* 顺序队列类型定义 */
    int  f, r;
    DataType  q[MAXNUM];
};
typedef  struct SeqQueue *PSeqQueue;	


PSeqQueue createEmptyQueue_seq( void ) {  
    PSeqQueue paqu;
    paqu = (PSeqQueue)malloc(sizeof(struct SeqQueue));
    if (paqu == NULL)
        printf("Out of space!! \n");
	else 
        paqu->f = paqu->r = 0;

    return paqu;
}

int  isEmptyQueue_seq( PSeqQueue paqu ) {
    return paqu->f == paqu->r;
}

/* 在队列中插入一元素x */
void  enQueue_seq( PSeqQueue paqu, DataType x ) {
    if( (paqu->r + 1) % MAXNUM == paqu->f  )
        printf( "Full queue.\n" );
    else {
        paqu->q[paqu->r] = x;
        paqu->r = (paqu->r + 1) % MAXNUM;
    }
}

/* 删除队列头元素 */
void  deQueue_seq( PSeqQueue paqu ) {
    if( paqu->f == paqu->r )
        printf( "Empty Queue.\n" );
    else
        paqu->f = (paqu->f + 1) % MAXNUM;
}

/* 对非空队列,求队列头部元素 */
DataType  frontQueue_seq( PSeqQueue paqu ) {
    return (paqu->q[paqu->f]);
}

/* 物品按性价比从新排序*/
void sort(int n, double p[], double w[]){
    int i, j;
    for (i = 0; i < n-1; i++)
        for (j = i; j < n-1; j++) {
            double a = p[j]/w[j];
            double b = p[j+1]/w[j+1];
            if (a < b) {
                double temp = p[j];
                p[j] = p[j+1];
                p[j+1] = temp;
                temp = w[j];
                w[j] = w[j+1];
                w[j+1] = temp;
            }
        }
}

/* 求最大可能值*/
double up(int k, double m, int n, double p[], double w[]){
    int i = k;
    double s = 0;
    while (i < n && w[i] < m) {
        m -= w[i];
        s += p[i];
        i++;
    }
    if (i < n && m > 0) {
        s += p[i] * m / w[i];
        i++;
    }
    return s;
}

/* 求最小可能值*/
double down(int k, double m, int n, double p[], double w[]){
    int i = k;
    double s = 0;
    while (i < n && w[i] <= m) {
        m -= w[i];
        s += p[i];
        i++;
    }
    return s;
}

/* 用队列实现分支定界算法*/
double solve(double m, int n, double p[], double w[], unsigned long* po){
    double min;
    PSeqQueue q = createEmptyQueue_seq();
    DataType x = {0,0,0,0,0,0};
    sort(n, p, w);
    x.max = up(0, m, n, p, w);
    x.min = min = down(0, m, n, p, w);
    if (min == 0) return -1;
    enQueue_seq(q, x);
    while (!isEmptyQueue_seq(q)){
        int step;
        DataType y;
        x = frontQueue_seq(q);
        deQueue_seq(q);
        if (x.max < min) continue;
        step = x.step + 1;
        if (step == n+1) continue;
        y.max = x.price + up(step, m - x.weight, n, p, w);
        if (y.max >= min) {
            y.min = x.price + down(step, m-x.weight, n, p, w);
            y.price = x.price;
            y.weight = x.weight;
            y.step = step;
            y.po = x.po << 1;
            if (y.min >= min) {
                min = y.min;
                if (step == n) *po = y.po;
            }
            enQueue_seq(q, y);
        }
        if (x.weight + w[step-1] <= m) {
            y.max = x.price + p[step-1] + 
                    up(step, m-x.weight-w[step-1], n, p, w);
            if (y.max >= min) {
                y.min = x.price + p[step-1] + 
                        down(step, m-x.weight-w[step-1], n, p, w);
                y.price = x.price + p[step-1];
                y.weight = x.weight + w[step-1];
                y.step = step;
                y.po = (x.po << 1) + 1;
                if (y.min >= min) {
                    min = y.min;
                    if (step == n) *po = y.po;
                }
                enQueue_seq(q, y);
            }
        }
    }
    return min;
}

#define n 4

double m = 15;
double p[n] = {10, 10, 12, 18};
double w[n] = {2, 4, 6, 9};

int main() {
    int i;
    double d;
    unsigned long po;
    d = solve(m, n, p, w, &po);
    if (d == -1)
        printf("No solution!\n");
    else {
        for (i = 0; i < n; i++)
            printf("x%d is %d\n", i + 1, ((po & (1<<(n-i-1))) != 0));
        printf("The max weight is %f\n", d);
    }
    getchar();
    return 0;
}