分支限界法求解最小重量机器问题

#include<iostream>
#include<queue>
#define INF 65535
#define MAXNUM 100
using namespace std;
class Shop{
//商店类
public:
double *w;
//该商店每个物品的的质量
double *v;
//该商店每个物品的价格
};
class Node{
public:
double tempv;
//当前价格
double tempw;
//当前质量
double lval;
//价格下界
double val;
//价格上界即优先级
int answer[MAXNUM];
//该节点的解
int depth;
//该节点的深度
friend
bool operator < (Node a,Node b){
return a.val > b.val;
}
};
class Machine{
public:
priority_queue<Node> q;
//优先队列小根堆
Shop *shop;
//商店指针
int num;
//商店个数
int parts;
//零件个数
double c;
//价格上界
double minsum;
//最小下届和
double bestw;
//最优解
int *bestanswer;
//最优解路径
double *minestw_each;
//每个零件的最小质量
public:
/* 初始化函数 */
void Initial(){
cout<<"please input the number of the shops and the number of the parts and the max cost: "<<endl;
cin>>num>>parts>>c;
shop = new Shop[num * 2];
bestanswer = new int[num * 2];
minestw_each = new double[parts * 2];
bestw = INF;
for(int i = 1;i <= num;i++){
shop[i].w = new double[parts * 2];
shop[i].v = new double[parts * 2];
}
cout<<"please input the cost of each parts: "<<endl;
for(int i = 1;i <= parts;i++)
for(int j = 1;j <= num;j++)cin>>shop[j].v[i];
cout<<"please input the weight of each parts: "<<endl;
for(int i = 1;i <= parts;i++)
for(int j = 1;j <= num;j++){
cin>>shop[j].w[i];
if(minestw_each[i] > shop[j].w[i])minestw_each[i] = shop[j].w[i];
}
minsum = 0;
for(int i = 1;i <= parts;i++)minsum += minestw_each[i];
for(int i = 1;i <= num;i++){
Node p;
p.depth = 1;
p.tempv = shop[i].v[1];
if(p.tempv < c){
p.tempw = shop[i].w[1];
p.answer[p.depth] = i;
p.lval = minsum - minestw_each[p.depth];
p.val = p.tempw + p.lval;
q.push(p);
}
}
}
/* 复制父节点的解路径 */
void Copy(Node &pre,Node &p){
for(int i = 1;i <= pre.depth;i++)p.answer[i] = pre.answer[i];
}
/* 保存最优路径 */
void Save(Node &p){
for(int i = 1;i <= parts;i++)bestanswer[i] = p.answer[i];
bestw = p.tempw;
}
/* 最小重量机器设计函数 */
void Design(){
while(!q.empty()){
Node pre = q.top();q.pop();
if(pre.depth == num - 1){
Node p;
p.depth = pre.depth + 1;
for(int i = 1;i <= num;i++)
if(pre.tempv + shop[i].v[p.depth] <= c && pre.tempw + shop[i].w[p.depth] < bestw){
Copy(pre,p);
p.answer[p.depth] = i;
p.tempw = pre.tempw + shop[i].w[p.depth];
Save(p);
q.push(p);
}
}
else if(pre.depth == num)return;
else{
for(int i = 1;i <= num;i++){
if(pre.tempv + shop[i].v[pre.depth + 1] < c){
Node p;
Copy(pre,p);
p.depth = pre.depth + 1;
p.tempw = pre.tempw + shop[i].w[p.depth];
p.tempv = pre.tempv + shop[i].v[p.depth];
p.lval = pre.lval - minestw_each[p.depth];
p.val = p.tempw + p.lval;
if(p.val < bestw){
p.answer[p.depth] = i;
q.push(p);
}
}
}
}
}
}
/* 显示结果 */
void Show(){
for(int i = 1;i <= parts;i++)cout<<"no."<<i<<" parts is bought by: "<<bestanswer[i]<<endl;
cout<<"the minest cost is: "<<bestw<<endl;
}
};
Machine m;
int main(){
m.Initial();
m.Design();
m.Show();
}

最后

以上就是缓慢书本为你收集整理的分支限界法求解最小重量机器问题的全部内容，希望文章能够帮你解决分支限界法求解最小重量机器问题所遇到的程序开发问题。

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