设某一机器由 n 个部件组成,每一种部件都可以从 m 个不同的供应商处购得。设 wij 是从供应商 j 处购得的部件 i 的重量,cij 是相应的价格。试设计算法,给出总价格不超过 d 的最小重量机器设计,输出最小重量,以及每个部件的供应商。
n=3,m=2,d=4;
w11=1, w12=2, w21=3, w22=2, w31=1, w32=2;
c11=3, c12=1, c21=1, c22=3, c31=1, c32=2。
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 105;
int n,m,d;
int bestw=0x3f3f3f3f;
int c[N][N], w[N][N],result[N];
struct Node
{
int cw; //当前零件的重量和
int cs; //当前零件的花费
int seller; //供应商
int level; //这次选择第几个零件
int priority; //小根堆的优先级
Node *father;
bool operator< (const Node& a) const
{
if (cw != a.cw) return cw>a.cw;
else if(level != a.level) return a.level<level;
else return true;
}
};
Node* leaf;//叶子结点,方便寻根
Node createNode(int level, Node* father, int seller, int cs, int cw){
Node newNode;
newNode.level = level;
newNode.father = father;
newNode.seller = seller;
newNode.cs = cs;
newNode.cw = cw;
return newNode;
}
void bfs()
{
priority_queue<Node> heap; //用优先队列,建立一个最小堆。我们已经重载了比较函数,但好像在vs里有问题,在dev没问题
Node h = createNode(0, NULL, 0, 0, 0);
heap.push(h);
while (heap.size())
{
Node* p = new Node(heap.top());
heap.pop();//队首元素作为父节点出队
if (p->level >= n)//到达叶节点,不能扩展 ,得到一个解
{
if (p->cw <bestw)
{
bestw = p->cw;
leaf = p; //记录最后是哪个结点,便于回溯找最优解
}
}
else
{
for (int i = 1; i <= m; i++)//扩展结点,依次选择每个售货商,m叉树
{
//约束函数剪枝和限界函数剪枝
if (p->cs + c[p->level+1][i] <= d && p->cw + w[p->level+1][i] <= bestw)
{
Node newNode = createNode(p->level + 1, p, i, p->cs + c[p->level + 1][i], p->cw + w[p->level + 1][i]);
heap.push(newNode);//儿子入队
//cout <<"供应商:"<< i <<' '<<"零件号:"<< newNode.level <<' '<<" 当前花费:"<< newNode.cs <<' '<<"当前重量:"<< newNode.cw << " "<<p->cw<<endl;
}
//else cout << "----------" << endl;
}
}
}
}
int main()
{
cin >> n >> m >> d;
leaf = NULL;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> c[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> w[i][j];
bfs();
cout << "最小重量为:" << bestw << endl;
for (int i = n; i >= 1; i--)
{
result[i] = leaf->seller;//从最后叶子结点回溯到根节点
leaf = leaf->father;
}
cout << "供应商为:";
for (int i = 1; i <= n; i++)
cout << result[i] << " ";
cout << endl;
return 0;
}
//测试样例:
/*
3 2 4
3 1 1 3 1 2
1 2 3 2 1 2
*/
算法设计作业,老师要求用分支限界做,感觉很有难度