5-4 最小重量机器设计问题 (20分)

 工作分配问题，最佳调度，最小重量机器设计问题是一样的

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

输入格式:

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

输出格式:

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

输入样例:

3 3 4
1 2 3
3 2 1
2 2 2
1 2 3
3 2 1
2 2 2

　　

输出样例:

在这里给出相应的输出。例如：

4
1 3 1 

代码：

#include <bits/stdc++.h>
using namespace std;
int n;  // n个部件 
int m;  // 每个部件m种选择
int MaxPrice;  // 允许的最高价格
int weight[40][40];  // weight[i][j] 表示 商家j 提供的 部件i 的重量
int price[40][40];   // price[i][j]  表示 商家j 提供的 部件i 的价格
int MinWeight=999999;
int BestRecord[40];  //最好路径，哪个部件用了哪些商家的货 
int PreRecord[40];   // Present Record,当前方案所选择的路径 , PreRecord[i]表示第i个部件选的商家 
int PrePrice = 0;    // 搜索时，当前总价格 
int PreWeight = 0;   // 搜索时，当前总重量 


void GetRecord()
{
    for(int i=1;i<=n;i++)
    {
        BestRecord[i] = PreRecord[i];
    }
}


void search(int dep) // 第dep个部件该选哪个商家 
{
    
    if(dep>n) {           //递归到叶子节点，说明当前价格PrePrice < MaxPrice 产生了一组解
        if(PreWeight < MinWeight ) 
        {
            MinWeight = PreWeight ;
            GetRecord();  // 获取路径 
        }
        return ; 
    } 
    
    for(int i=1;i<=m;i++)  // 分别对用m个商家的部件的情况进行讨论 
    {
        PrePrice = PrePrice + price[dep][i];
        PreWeight = PreWeight + weight[dep][i];
        PreRecord[dep] = i; 
        if( PreWeight < MinWeight && PrePrice <= MaxPrice )   search(dep+1);
        PrePrice = PrePrice - price[dep][i];
        PreWeight = PreWeight - weight[dep][i];
    }
    
    return ;
}


int main()
{
   
   cin>>n>>m>>MaxPrice;    
   
   for(int i=1;i<=n;i++){
           for(int j=1;j<=m;j++){
               cin>>price[i][j];
       }
   }
   
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
               cin>>weight[i][j];
       }
   }
   
   search(1);
   
   cout<<MinWeight<<endl;
   
   for(int i=1;i<=n;i++)
   {
       cout<<BestRecord[i]<<" ";
   }
   
   return 0;
}