第五章实验报告

一.题目

7-2 最小重量机器设计问题 (25 分)  

设某一机器由n个部件组成,每一种部件都可以从m个不同的供应商处购得。设wij​是从供应商j 处购得的部件i的重量,cij​是相应的价格。 试设计一个算法,给出总价格不超过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 <iostream>
using namespace std;   int n; int m; int d; int w[1000][1000]; int c[1000][1000]; int minw=100000000; int curw=0; int curc=0; int minx[1000]; int x[1000];   void backtrack(int t){ if(t>n){ if(curw<minw){ minw=curw; for(int i=1; i<=n; i++){ minx[i]=x[i]; } } } else{ for(int i=1; i<=m; i++){ curc+=c[t][i]; curw+=w[t][i]; x[t]=i;   if(curc<=d && curw<minw){ backtrack(t+1); }   curc-=c[t][i]; curw-=w[t][i]; x[t]=0; } } }   int main(){ cin>>n>>m>>d;   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]; } }   backtrack(1); cout<<minw<<endl; for(int i=1; i<=n; i++){ cout<<minx[i]<<" "; } cout<<endl; return 0; }  二理解 回溯法(探索与回溯法)是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法
上一篇:python-路由Routers-SimpleRouter-DefaultRouter的使用


下一篇:java让程序休眠的两种方式