#include<iostream>
#include<queue>
using namespace std;
int n,m,d;
int MinWeight;
int **c = NULL;
int **w = NULL;
struct Node
{
int weight;//当前已选机器的重量和
int val;//当前已选机器的价值和
int source; //哪个供货商
int level; //第几层
int priority; //优先级
Node *father;
};
//优化的优先级设定
bool operator<(Node a,Node b) //level按照减序
{
if(a.priority == b.priority)return a.level <b.level; //如果重量相同，选择level大的。
return a.priority > b.priority;//否则，重量小的先出队
}
void QueuePriority(Node a)
{
int temp_min_w= INT_MAX;
//int temp_min_c = INT_MAX;
for(int i=a.level+1 ; i<=n ; i++)//选出剩余的部件在售货商中购买的最小质量,就是选择每一层最小的质量
{
for(int j=1;j<=m;j++) //每一层找最小的
{
temp_min_w = temp_min_w<w[i][j]?temp_min_w:w[i][j];//从m个商家中选择当层重量最小的
//temp_min_c = temp_min_c<c[i][j]?temp_min_c:c[i][j];//从m个商家中选择当层价格最小的
}
}
a.priority =a.val+ temp_min_w;
}
Node *MinLeaf;//叶子结点
void MinWeightMachine()
{
int i,j;
MinWeight = INT_MAX;
Node initial;
initial.father = NULL;
initial.level = 0;
initial.source=0;
initial.val = 0;
initial.weight = 0;
QueuePriority(initial);//计算优先级
priority_queue<Node>heap; //用优先队列，建立一个最小堆。加入进去就会自动排好序的。
heap.push(initial);
while(!heap.empty())
{
Node *fartherNode = new Node(heap.top());
heap.pop();//队首元素作为父节点出队，即优先级值小的活结点先扩展
if(fartherNode->level == n)//到达叶节点，不能扩展 ,得到一个解
{
if(fartherNode->weight <MinWeight) //更新
{
MinWeight = fartherNode -> weight;
//MinValue = fartherNode ->val;
MinLeaf = fartherNode; //记录是最后是哪个结点数据,便于回溯找最优解
}
}
else
{
for(i=1;i<=m;i++)//扩展结点，依次选择每个售货商，每次都是m叉树
{
if(fartherNode->val+c[fartherNode->level +1][i] <=d ||fartherNode->weight +w[fartherNode->level +1][i] <= MinWeight)
{//可行性剪枝和限界剪枝
Node *newNode = new Node;//生儿子结点
newNode->level = fartherNode->level +1;//层次加1
newNode->father = fartherNode;
newNode->source = i;
newNode->val = fartherNode->val + c[newNode->level][i];
newNode->weight = fartherNode->weight + w[newNode->level][i];
QueuePriority(initial);
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] = new int [m+1];
c[i] = new int [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;
}
