【题目描述】

设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设Wij 是 

从供应商j处购得的部件i的重量，Cij 是相应的价格。 

试设计一个算法，给出总价格不超过c的最小重量机器设计。 

′编程任务： 

对于给定的机器部件重量和机器部件价格，编程计算总价格不超过d的最小重量机器设 

计。

【输入描述】

第一行有 3 个正整数 n ，m和 d。接下来的 2n 行，每 

行m个数。前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

【题目分析】

1. 可以考虑深搜的解法

2.由于题目已经给出总价格的上限，因此算法通过使用回溯来选择合适的机器使得在总价格不超过d时得到的机器重量最小。首先初始化当前价格cp=0,当前重量cw=0,此外，还要设置一个变量bestw表示选择机器的总重量，初始化其为每个部件从1号供应商购买的重量。在循环选择i号机器时，判断从j号供应商购买机器后的价格是否大于总价格，如果不大于则选择，否则不选，继续选择下一供应商进行判断。在得到一个合适的供应商后，继续选择下一机器的供应商，从第一个选到最后一个供应商。当所有机器选择结束后，判断得到的总重量是否比之前的bestw小，如果小就赋给bestw，然后从这一步开始，回溯到上一机器，选择下一合适供应商，继续搜索可行解，直到将整个排列树搜索完毕。这样，最终得到的bestw即为最优解。 

     当然，考虑到算法的时间复杂度，还可以加上一个剪枝条件，即在每次选择某一机器时，再判断选择后的当前重量是否已经大于之前的bestw，如果大于就没必要继续搜索了，因为得到的肯定不是最优解。 

3、算法设计： 

a.部件有n个，供应商有m个，分别用array2[i][j]和array1[i][j]存储从供应商j 处购得的部件i的重量和相应价格，d为总价格的上限。 

b.用递归函数machine(i)来实现回溯法搜索排列树（形式参数i表示递归深度）。 

  ① 若cp>d，则为不可行解，剪去相应子树，返回到i-1层继续执行。 

  ② 若cw>=bestw，则不是最优解，剪去相应子树，返回到i-1层继续执行。 

  ③ 若i>n，则算法搜索到一个叶结点，用bestw对最优解进行记录，返回到i-1层继续执行； 

  ④ 用for循环对部件i从m个不同的供应商购得的情况进行选择(1≤j≤m）。 

c.主函数调用一次machine(1)即可完成整个回溯搜索过程，最终得到的bestw即为所求最小总重量。 

【参考代码】

#include<bits/stdc++.h>  using namespace std;  int n,m,d;  int array1[100][100];//cij  int array2[100][100];//wij  int cw=0;  int cp=0;  int bestw=1000000;  int x[100];//记录所选部门  int x1[100];  void machine(int t){      if(t>=n){          if(cw<bestw){              bestw=cw;              for(int i=0;i<n;i++){                  x1[i]=x[i];              }          }          return;      }     for(int i=0;i<m;i++){         cp+=array1[t][i];         cw+=array2[t][i];         x[t]=i;        if(cp<=d && cw <=bestw){          machine(t+1);        }        cp-=array1[t][i];        cw-=array2[t][i];     }  }  int main()  {        cin >> n >> m >> d;      memset(x1,0,sizeof(x1));      memset(x,0,sizeof(x));      memset(array1,0,sizeof(array1));      memset(array2,0,sizeof(array2));      for(int i=0;i<n;i++){          for(int j=0;j<m;j++){              cin >> array1[i][j];          }      }       for(int i=0;i<n;i++){          for(int j=0;j<m;j++){              cin >> array2[i][j];          }      }      machine(0);      cout << bestw << endl;       for(int i=0;i<n;i++){          cout << x1[i]+1 << " ";       }      return 0;  }

(adsbygoogle = window.adsbygoogle || []).push({});