算法第五章上机实验报告

1. 回溯法的方法分析“最小重量机器设计问题”

题目:

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

 1.1 说明“最小重量机器设计问题"的解空间

{{1,3,1},{1,3,2},{1,3,3}}

 1.2 说明 “最小重量机器设计问题"的解空间树

 解空间树是一个m叉子集树

1.3 在遍历解空间树的过程中,每个结点的状态值是什么

 当前的总价值和总重量

代码:

#include<bits/stdc++.h>

using namespace std;
int n, m, d;
int c[1000][1000], w[1000][1000];
int x[1000];
int p[1000];
int cw = 0, cc = 0, wmin = 1e9;
void backtrack(int t) {
if(t > n) {
wmin = cw;
for(int i = 1; i <= n; i++) {
p[i] = x[i];
}
return;
}
for(int i = 1; i <= m; i++) {
if(cc + c[t][i] <= d && cw + w[t][i] < wmin) {
 x[t] = i;
cw += w[t][i];
cc += c[t][i];
backtrack(t + 1);
cw -= w[t][i];
cc -= c[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 << wmin << endl;
for(int i = 1; i <= n; i++) {
cout << p[i] << " ";
}
 return 0;
}

2. 你对回溯算法的理解

回溯法百度上的定义是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。 但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法。我觉得回溯法就像是在走迷宫吧,走到行不通了地方就回到上一个分岔路口,最后将所有可行的路线找出来再取其中的最优解。 

上一篇:2021-2022-1 20211428《信息安全专业导论》第5周学习总结


下一篇:第四章 分支结构程序设计习题2