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

概述

问题描述:

设某一机器由n个部件组成,每一种部件都可以从m个不同的供应商处购得。设是从供应商j处购得的部件i的重量,是相应的价格。试设计一个优先队列式分支限界法,给出总价格不超过d的最小重量机器设计。

[之所以想记录这个问题,是因为我觉得自己"用各个部件的最小重量作为未来最理想重量"的这个设计还挺特别。其他都是实验报告中的内容]

算法描述:

算法实现:

#include<stdio.h>
#include<stdlib.h>
struct NodeType
{
int *mark;
//记录部件i的供应商
int preview;
//当前已买部件重量+未来最理想重量
int now;
//当前考虑买的部件
int nowd;
//当前已买部件价格
struct NodeType* next;
};
#define MAXINT 65534;
int doit(int n,int m,int d,int **w,int **c,int *future)
{
int frist=0;
while(frist<m&&c[0][frist]>d)
frist++;
//找第一个部件的不超过价格上限的供应商frist
if(frist==m)return 0;
//第一个部件的所有供应商的价格都超过价格上限,无法购买
/*
构造优先队列的第一个结点
*/
struct NodeType *h,*t,*temp;
h=t=temp=temp=(struct NodeType *)malloc(sizeof(struct NodeType));
temp->mark=(int *)malloc((sizeof(int))*n);
   temp->preview=future[0]+w[0][frist];
//当前已买部件重量+未来最理想重量
temp->now=0;
//当前考虑买的部件为部件0
   temp->nowd=c[0][frist]; //当前已买部件价格(部件0在供应商frist处购买的价格)
temp->mark[0]=frist;
//部件0在供应商frist处购买
temp->next=NULL;
for(int i=frist+1;i<m;i++)
{
if(c[0][i]<=d)
//若在供应商i处购买部件0的价格没有超过价格上限(约束剪枝)
{
temp=(struct NodeType *)malloc(sizeof(struct NodeType));
temp->mark=(int *)malloc((sizeof(int))*n);
temp->preview=future[0]+w[0][i];//当前已买部件重量+未来最理想重量
temp->now=0;
//当前考虑买的部件为部件0
temp->nowd=c[0][i]; //当前已买部件价格(部件0在供应商i处购买的价格)
temp->mark[0]=i;
//部件0在供应商i处购买
temp->next=NULL;
t->next=temp;
t=t->next;
}
}
int realmin=MAXINT;
//记录最小重量
int *markmin;
markmin=(int *)malloc((sizeof(int))*n);
  //记录部件i的供应商markmin[i]
struct NodeType *minr,*minp,*r,*q;
while(h!=NULL)
{
/*
找到队列中重量最小的结点作为扩展结点(minp)
*/
int min=realmin;//-
r=q=h;
while(q!=NULL)
{
if(q->preview<min)
{
min=q->preview;
minr=r;
minp=q;
}
r=q;
q=q->next;
}
for(int i=0;i<m;i++)
{
if(minp->nowd+c[minp->now+1][i]<=d)
//若已买部件价格加上在供应商i处购买
       //部件minp->now+1的价格小于等于价格上限

{
temp=(struct NodeType *)malloc(sizeof(struct NodeType));
temp->mark=(int *)malloc((sizeof(int))*n);
/*
当前已买部件重量+未来最理想重量
*/
temp->preview=0;
for(int j=0;j<(minp->now+1);j++)
temp->preview+=w[j][minp->mark[j]];
          //先计入之前已买的部件的重量
temp->preview+=w[minp->now+1][i];
          //在计入当期在供应商i处购买部件minp->now+1的重量
temp->preview+=future[minp->now+1];
          //最后计入未来最理想的重量
temp->now=minp->now+1;

          //当前考虑买的部件为部件minp->now+1 temp->nowd=minp->nowd+c[minp->now+1][i];        //当前之前已买部件价格+在供应商i处购买部件           //minp->now+1的价格 /* 记录之前已买部件的供应商+当前部件的供应商i */ for(int j=0;j<(minp->now+1);j++) temp->mark[j]=minp->mark[j]; temp->mark[minp->now+1]=i; temp->next=NULL; if(temp->now+1==n&&temp->preview<realmin)           //若当前考虑的部件已经是最后一个部件,           //且在供应商i处购买这个部件, //能够使得现在部件总重量优于当前求解出的最优值 { /*记录最优值和最优解*/ realmin=temp->preview; for(int j=0;j<n;j++)markmin[j]=temp->mark[j]; free(temp); } else { //若当前考虑的部件并非最后一个部件,将此结点加入队列 t->next=temp; t=t->next; } } } if(minp==h)//拓展结点为头结点 { h=h->next; free(minp);//将拓展结点释放 } else //拓展结点非头结点 { minr->next=minp->next; free(minp);//将拓展结点释放 } /* 如果当前队列中的结点的最理想重量大于已经求出的最优解,则将该结点释放 */ while(h->preview>=realmin&&h!=t) { q=h; h=h->next; free(q); } if(h->preview>=realmin) { free(h); h=NULL; } } /* 输出最优值及最优解 */ printf("%dn",realmin); for(int i=0;i<n;i++)printf("%d ",markmin[i]+1); return 0; } int main() { int n,m,d; scanf("%d %d %d",&n,&m,&d);//部件数,供应商数,价格上限 int ** c; c=(int **)malloc((sizeof(int *))*n); for(int i=0;i<m;i++) c[i]=(int *)malloc((sizeof(int))*m); for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("%d",&c[i][j]); //在供应商j处购买部件i的价格c[i][j] int ** w; w=(int **)malloc((sizeof(int *))*n); for(int i=0;i<m;i++) w[i]=(int *)malloc((sizeof(int))*m); for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("%d",&w[i][j]); //在供应商j处购买部件i的重量w[i][j] int * future; future=(int *)malloc((sizeof(int))*n); for(int i=0;i<n;i++) { int min=MAXINT; for(int j=0;j<m;j++ ) if(min>w[i][j]) min=w[i][j]; future[i]=min; } for(int i=0;i<n-1;i++) { future[i]=0; for(int j=i+1;j<n;j++) future[i]+=future[j]; } future[n-1]=0; //购买完部件i后剩余部件的最理想重量 doit(n,m,d,w,c,future); //优先队列分支限界算法 return 0; }

 

转载于:https://www.cnblogs.com/kk980414/p/9787041.html

最后

以上就是文艺裙子为你收集整理的优先队列式分支限界法-最小重量机器设计问题的全部内容,希望文章能够帮你解决优先队列式分支限界法-最小重量机器设计问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(37)

评论列表共有 0 条评论

立即
投稿
返回
顶部