算法(五)-装载问题分支限界法

问题描述：

 

代码

#include <iostream>
#include <queue>
using namespace std;

class Loading
{
public:
    void getBestWeight();//获取最优值
private:
    int maxLoading();//求出最优值
    void init();//初始化数据
    void enQueue(int);//判断是否到达叶结点
private:
    int n;//物品的个数
    int *weight;//每个物品的重量
    queue<int> q;//队列
    int nowWeight;//当前结点所对应的载重量
    int bestWeight;//当前最优的载重量
    int level;//当前层数
    int c;//船的载重量
};

void Loading::getBestWeight()
{
    init();
    cout<<"最大载重量是 = "<<maxLoading()<<endl;
    delete[] weight;
}

void Loading::init()
{
    cout<<"请输入有多少个物品: "; cin>>n;
    cout<<"请输入有多少船的载重量: "; cin>>c;
    cout<<"请输入每个物品的重量: ";
    weight = new int[n+1];
    weight[0] = 0;
    for(int i = 1; i <= n; i++) cin>>weight[i];
    nowWeight = 0;
    bestWeight = 0;
    level = 0;
}

void Loading::enQueue(int wt)
{
    if(level == n)//到达叶结点
    {
        if(wt > bestWeight)
            bestWeight = wt;
    }
    else
    {
        q.push(wt);//加进队列
    }
}

int Loading::maxLoading()
{
    q.push(-1);
    level = 1;
    while(true)
    {
        if(nowWeight + weight[level] <= c)//左儿子结点是否能装进船
            enQueue(nowWeight+weight[level]);
        enQueue(nowWeight);//右儿子节点没有将物品装进船，所以不用判断
        nowWeight = q.front();//取出结点
        q.pop();
        if(nowWeight == -1)//完成一层的取物品重量
        {
            if(q.empty())
                return bestWeight;
            q.push(-1);
            nowWeight = q.front();//取出
            q.pop();
            level++;//进入下一层
        }
    }
}

int main()
{
    Loading load = Loading();
    load.getBestWeight();
    system("pause");
    return 0;
}

装载问题分支限界法改进算法

/*
测试数据：
n = 3 c1 = c2 = 50
w = [10, 40, 40]
*/

#include <iostream>
#include <queue>
using namespace std;

class Loading
{
public:
    void getBestWeight();//获取最优值
private:
    int maxLoading();//求出最优值
    void init();//初始化数据

private:
    int n;//物品的个数
    int *weight;//每个物品的重量
    queue<int> q;//队列
    int nowWeight;//当前结点所对应的载重量
    int bestWeight;//当前最优的载重量
    int level;//当前层数
    int c;//船的载重量
    int restWeight;//剩余集装箱的重量 
};

void Loading::getBestWeight()
{
    init();
    cout<<"最大载重量是 = "<<maxLoading()<<endl;
    delete[] weight;
}

void Loading::init()
{
    cout<<"请输入有多少个物品: "; cin>>n;
    cout<<"请输入有多少船的载重量: "; cin>>c;
    cout<<"请输入每个物品的重量: ";
    weight = new int[n+1];
    weight[0] = 0;
    for(int i = 1; i <= n; i++) cin>>weight[i];
    nowWeight = 0;
    bestWeight = 0;
    level = 0;
    restWeight = 0;
}

int Loading::maxLoading()
{
    q.push(-1);
    level = 1;
    for(int i = 2; i <= n; i++)
        restWeight += weight[i];
    int leftWeight = 0;//左儿子的重量
    while(true)
    {
        leftWeight = nowWeight + weight[level];
        if(leftWeight <= c) { if(leftWeight > bestWeight)
                bestWeight = leftWeight;
            if(level < n) q.push(leftWeight); } if(nowWeight + restWeight > bestWeight && level < n)
            q.push(nowWeight);
        nowWeight = q.front();
        q.pop();
        if(nowWeight == -1)
        {
            if(q.empty())
                return bestWeight;
            q.push(-1);
            nowWeight = q.front();
            q.pop();
            level++;
            restWeight -= weight[level];
        }
    }
}

int main()
{
    Loading load = Loading();
    load.getBestWeight();
    system("pause");
    return 0;
}

装载问题分支限界法，求出最优解，使用节点加入队列

 

#include <iostream>
#include <queue>
using namespace std;

class QNode
{
public:
    void getMaxLoading();
private:
    void init();
    void enQueue(int,bool);
    int maxLoading();
    void destructorArray();
private:
    int n;//物品数
    int *w;//各个物品的重量
    int nowWeight;//当前扩展结点的重量
    int bestWeight;//最优载重量
    int restWeight;//剩余重量
    int c;//船的载重量
    int level;//当前层数
    QNode *nowNode;//当前扩展结点
    QNode *bestNode;//最优扩展结点
    QNode *parent;//指向扩展结点的指针
    bool lChild;//左儿子标志
    bool *answer;//最优解
    queue<QNode *> q;
};

/*释放空间*/
void QNode::destructorArray()
{
    delete[] w;
    delete[] answer;
}

/*获取最优值*/
void QNode::getMaxLoading()
{
    init();
    cout<<"最优载重量为: "<<maxLoading()<<endl;
    cout<<"最优解为: "<<endl;
    for(int i = 1; i <= n; i++)
        if(answer[i])
            cout<<w[i]<<" "<<"i = "<<i<<endl;
    cout<<endl;
    destructorArray();
}

/*计算队列最优值*/
int QNode::maxLoading()
{
    q.push(0);
    level = 1;

    int addQueueWeight = 0;
    while(true)
    {
        /*加入队列*/
        addQueueWeight = nowWeight + w[level];
        if(addQueueWeight <= c)//小于船重 { if(addQueueWeight >= bestWeight)//大于最优值，更新最优值
                bestWeight = addQueueWeight;
            enQueue(addQueueWeight, true);//加入左儿子结点
        }
        if(nowWeight + restWeight >= bestWeight)
            enQueue(nowWeight, false);//加入右儿子结点

        /*以下是从队列中拿出元素*/
        nowNode = q.front();
        q.pop();//获取队列首部
        if(!nowNode)//同层结点尾部
        {
            if(q.empty())
                break;
            q.push(0);
            nowNode = q.front();
            q.pop();
            level++;
            restWeight -= w[level];
        }
        
        /*更新当前重量，现在的重量为当前结点的重量*/
        nowWeight = nowNode->nowWeight;
    }

    for(int i = n-1; i >= 1; i--)
    {
        answer[i] = bestNode->lChild;
        bestNode = bestNode->parent;
    }
    return bestWeight;
}

/*加入队列*/
void QNode::enQueue(int addQueueWeight, bool ch)
{
    //当层次到达n层时，判断获取最优解的叶结点
    if(level == n)
    {
        if(addQueueWeight == bestWeight)
        {
            bestNode = nowNode;
            answer[n] = ch;
        }
        return;
    }
    //b为当前结点的下一层结点
    QNode *b;
    b = new QNode;
    b->nowWeight = addQueueWeight;
    b->parent = nowNode;
    b->lChild = ch;
    q.push(b);
}

/*初始化类中成员变量*/
void QNode::init()
{
    //输入
    cout<<"请输入物品数: "<<endl; cin>>n;
    cout<<"请输入船的载重量: "<<endl; cin>>c;
    cout<<"请输入各个物品的重量: "<<endl;
    w = new int[n+1];
    w[0] = 0;
    for(int i = 1; i <= n; i++) cin>>w[i];

    //变量初始化
    bestWeight = 0;
    nowWeight = 0;
    nowNode = 0;
    answer = new bool[n+1];
    for(int i = 0; i <= n; i++)
        answer[i] = false;
    restWeight = 0;
    for(int i = 2; i <= n; i++)
        restWeight += w[i];
}

int main()
{
    QNode qNode = QNode();
    qNode.getMaxLoading();
    system("pause");
    return 0;
}