#分支限界法#最小机器重量设计问题（优先队列）

75 阅读 0 评论 50 点赞

我是靠谱客的博主失眠魔镜，最近开发中收集的这篇文章主要介绍#分支限界法#最小机器重量设计问题（优先队列），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

(⊙o⊙)…，一部分注释的代码直接被吞了~汗~坑~有空再折腾

仅是学习算法时使用一下~（个人感觉不是个多好用的算法，毕竟写起来就很麻烦）

题目：

设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设w[i][j]是从供应商j处购得的部件i的重量，c[i][j]是相应的价格，给出总价格不超过d的最小重量机器设计。

算法设计：

对于给定的机器部件重量和机器部件价格，计算总价格不超过d的最小重量机器设计、

数据输入：

第一行有3个整数，n,m,d。接下来2n行，每行n个数，前n行是c，后n行是w

数据输出：

将计算出的最小重量，以及每个部件的供应商输出

其实自己的优先队列priority_queue的优先级设定是有个改进的空间的。

优先级的设定，当队列中有两个结点的重量是相同的时候，那么设定为，level大的优先级就更高一点，也就是说，更接近于叶子结点的那个结点更优先。目的就是为了更快的刷新出最小的重量，方便后面的剪枝。如果说没有两个结点重量相同，那就重量更小的优先。

优先级优化思路：类似于旅行售货商问题的优先级设定，记录剩余的未购买原件中的，单个原件购买的最小价值之和。

就是：

物品1 ： 3 2 1

物品2 ： 2 5 3

物品3 ： 2 3 1

假如，物品1已经入队了，且当前重量为3,剩余的最小重量之和为2+1 = 3（物品2和物品3中）总和为5

然后，假如物品2，已经入队了，且当前重量为1+3 =4（第一个物品选择的是1，第二个物品选择的是2），剩余最小重量和为1，总和为5。

也就是说，先执行的其实就是第二个方案。

这种优先级的设定，对于处于不同level的结点，还是有一定的优化作用，毕竟目的就是为了，最快，最先找到一个最小重量，便于后面的剪枝操作。

C++语言

#include<iostream>


using 
namespace 
std;


int n
,
m
,
d;


int 
MinWeight;


int 
MinValue;


int 
**
c  

=
NULL;


int 
**
w
=
NULL;




struct 
Node


{

  
  

int
 weight;

  
  

int
 val;

  
  

int
 source;  

//哪个供货商

  
  

int
 level;  
 
  
  

//第几层

  
  

Node
 *
father;


};




//原始的优先级设定








//优化的优先级设定


bool 
operator
<(Nodea,Node b)  //level按照减序
 {
    if(a.weight== b.weight)returna.level<b.level;   //如果质量相同，选择level大的。
    //选择比较大的level，相当于用到了一定的回溯思想，只是想最早找到那个MinWeight
    return  a.weight> b.weight;
 }
 
 
 
 Node *MinLeaf;
 void MinWeightMachine()
 {
    int  i,j;
    MinValue  = INT_MAX;
    MinWeight  = INT_MAX;
    Node  intital;
    intital.father  =NULL;
    intital.level=0;
    intital.source=0;
    intital.val=0;
    intital.weight=0;
 
    priority_queue<Node>heap;  //用优先队列，建立一个最小堆。加入进去就会自动排好序的。
    heap.push(intital);
    while(!heap.empty())
    {
       Node *fartherNode = newNode(heap.top());
       heap.pop();
       if(fartherNode->level== n)
       {
          if(fartherNode->weight<MinWeight)  //最开始给MinWeight赋一个较大的值
          {
              MinWeight=fartherNode->weight;
              MinValue  =fartherNode->val;
              MinLeaf=fartherNode;           //记录是最后是哪个结点数据
          }
       }
       else
       {
       
          int min_w=INT_MAX,   
              min_c=INT_MAX;
          //min_w分别代表当前的质量加上剩余的最小质量的和，min_c代表当前价值加上剩余的最小价值的和
          min_c=fartherNode->val;
          min_w=fartherNode->weight;
           
          for(i = fartherNode->level+1;i<=n ;i++)//选出剩余的部件在售货商中购买的最小质量,就是选择每一层最小的质量
          {
              int temp_min_w=INT_MAX,
                   temp_min_c=INT_MAX;
              for(j=1;j<=m;j++)   //,temp_min记录当前这一层的最小的质量
              {
                 temp_min_w=temp_min_w < w[i][j]?temp_min_w:w[i][j];
                 temp_min_c=temp_min_c < c[i][j]?temp_min_c:c[i][j];
              }
              min_w  += temp_min_w;
              min_c  += temp_min_c;
          }
           
         
          if(min_w>MinWeight||min_c>d)
          {
              
              continue;
          }
       
          for(i=1;i<=m ;i++)   //依次选择每个售货商
          {
              if(fartherNode->val  +c[fartherNode->level+1][i]<=d ||fartherNode->weight  +w[fartherNode->level+1][i]<=MinWeight)
              {
                 Node *newNode=newNode;
                 newNode->level=fartherNode->level+1;
                 newNode->father=fartherNode;
                 newNode->source=i;
                 newNode->val=fartherNode->val+c[newNode->level][i];
                 newNode->weight=fartherNode->weight+w[newNode->level][i];
                 heap.push(*newNode);
              }
          }
       }
    }
 
 }
 
 int main()
 {
    int  i,j;
    cout<<"请分别输入，部件个数，供应商个数，及最大的总价格："<<endl;
    cin>>n>>m>>d;
    w  = new  int*[n+1];
    c  = new  int *[n+1];
    for(i=1;i<= n ;i++)
    {
       w[i]  =newint[m+1];
       c[i]=newint[m+1];
    }
    MinLeaf  = NULL;
    
    cout<<"请依次输入各个部件在各个供应商处购买的价格:"<<endl;
    for(i=1 ;i<= n ;i++)
       for (j=1 ;j<=m ;j ++)
          cin>>c[i][j];
    cout<<"请依次输入各个部件在各个供应商处购买的重量:"<<endl;
    for(i=1;i<=n;i++)
       for(j=1;j<=m;j++)
          cin>>w[i][j];
    MinWeightMachine();
    cout<<"最小质量为:"<<MinWeight<<endl;
    int  *result  = new  int[n+1];
    for(i=n;i>=1;i--)
    {
       result[i]=MinLeaf->source;
       MinLeaf=MinLeaf->father;
    }
    cout<<"各个部件的来源分别为:"<<endl;
    for(i=1;i<=n;i++)
       cout<<result[i]<<"";
    cout<<endl;
 }
 
 
 
 