算法第五章最小重量机器设计问题

1、题目名称:最小重量机器设计问题

 

2、问题描述:

设某一机器由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 

3、算法描述

#include <iostream>
using namespace std;
int w[30][30];
int c[30][30];

int n, m, d;
int cw = 0;
int cc = 0;
int bestw = 0x7fffffff;
int x[30];
int bestx[30];

void backtrack(int t) {
if (t > n) {
if (cw < bestw) {
bestw = cw;
for (int i = 1; i <= n; i++)
bestx[i] = x[i];
}
return;
}

for (int i = 1; i <= m; i++) {
x[t] = i;
cw += w[t][i];
cc += c[t][i];
if (cc <= d && cw < bestw) {
backtrack(t+1);
}
cc -= c[t][i];
cw -= w[t][i];
}
}

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 << bestw << endl;
for (int i = 1; i <= n; i++)
cout << bestx[i] << " ";
cout << endl;

return 0;
}

 

4、

4.1解空间

以样例为例写出解空间:

(i,j,k)表示第1个部件选择第i个供应商,第2个部件选择第j个供应商,第3个部件选择第k个供应商,以此类推。

(1,1,1)(1,1,2)(1,1,3)

(1,2,1)(1,2,2)(1,2,3)

(1,3,1)(1,3,2)(1,3,3)

(2,1,1)(2,1,2)(2,1,3)

(2,2,1)(2,2,2)(2,2,3)

(2,3,1)(2,3,2)(2,3,3)

(3,1,1)(3,1,2)(3,1,3)

(3,2,1)(3,2,2)(3,2,3)

(3,3,1)(3,3,2)(3,3,3)

4.2  每个结点的状态值是该点的重量w和价格c。

5、对回溯算法的理解

回溯法解题时通常包含3个步骤:

①针对所给问题,定义问题的解空间;

② 确定易于搜索的解空间结构;

③以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。

 
上一篇:Cypher 入门笔记


下一篇:nuxt项目表格多选table,input传参并选中input type=“checkbox“原生js