目录

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

 最小重量机器设计问题描述

问题描述：

输入格式:

输出格式:

输入样例:

输出样例：

回溯法的基本步骤：

常用剪枝函数：

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

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

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

1.4 代码

2. 你对回溯算法的理解

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

 最小重量机器设计问题描述

问题描述：

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

输入格式:

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

输出格式:

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

输入样例:

1
2
3
4
5
6
7
8
3 3 4
1 2 3
3 2 1
2 2 2
1 2 3
3 2 1
2 2 2

输出样例：

1
2
4
1 3 1 

回溯法的基本步骤：

        （1）针对所给问题，定义问题的解空间；

        （2）确定易于搜索的解空间结构；

        （3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索

常用剪枝函数：

        用约束函数在扩展结点处剪去不满足约束的子树；

        用限界函数剪去得不到最优解的子树。

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

        理解问题：一共购置n个部件，每个部件可以从m个供应商手中获得，故每个部件有m中选择。

所有可能结果：

{1， 1， ……，1}、{2， 1， ……，1}、{3， 1， ……， 1}

  ……

{m，m，……，m}  

每个大括号里一共n个数字，对应n个部件，取值从1到m对应m个供应商，每个部件都分别有m种可能的选择，一共有m^n种可能的结果。

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

        不剪枝看，这棵解空间树是一棵m叉树，一共n层，第几层结点的状态值就对应第几个部件的选择，是哪个供应商；添加剪枝函数，使得该树被剪枝，删去不满足价格小于d以及得不到最优解的可能，最终使得整体在满足价格不超过d的条件下购置n个商品的最小重量。

剪枝函数：

        约束函数contains()：满足当前已购置商品的价格不超过d

        限界函数bound()：判断当前已购置商品的重量不会超过已获得的最优解（价格不超过d条件下的最小重量），如果超过了，则不用再往下遍历该结点了，肯定得不到最优解，回溯看上一步选择其他值是否可能得到最优解。

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

        假设该结点是第i层的结点，同时该结点的值为j，表示状态为第i个部件选择在第j个供应商处购置。

1.4 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
using namespace std;
int n; // n个部件
int m; // m个供应商
int w[30][30];
// w[i][j]：从供应商j处购得部件i的重量
int c[30][30];
// c[i][j]：从供应商j处购得部件i的价格
// 1 <= i <= n ; 1 <= j <= m
int x[30], bestx[30];
// 1到n个部件分别选择的供应商
int leastw = 0x3f3f3f3f;
// 预算d条件下购置n个部件的最小重量
int cw;
// 当前重量
int cost;
// 当前价格
int d;
// 总价格不超过d
bool contains(int t) { // 限界
return (cost + c[t][x[t]] <= d);
}
bool bound(int t) {
return (cw + w[t][x[t]] < leastw);
}
void backtrack(int t) { // 依次判断1到n个部件
if(t > n) {
if(cw < leastw) {
leastw = cw;
for(int i = 1; i <= n; i++)
bestx[i] = x[i];
}
return;
}
for(int i = 1; i <= m; i++) { // 依次观察m个供应商
x[t] = i;
if(contains(t) && bound(t)) {// 剪枝：价格小于d条件下，重量尽可能小
cost += c[t][x[t]];
cw += w[t][x[t]];
backtrack(t+1);
cost -= c[t][x[t]];
cw -= w[t][x[t]];
}
}
}
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 << leastw << endl;
for(int i = 1; i <= n; i++) {
cout << bestx[i] << " ";
}
}

2. 你对回溯算法的理解

        目前我所学过的解空间树分为子集树、排列树和n叉树（最小重量机器设计问题），思想都大致相同，像是“试错”，把每种可能的结果走一遍，不行（用剪枝函数）或到叶子结点就回溯，继续看另一种结果是否可以获得想要的结果。

        我目前写代码的步骤，首先是把所有可能的结果都想到，构建解空间；之后是将所有可能的结果在一棵解空间树上体现出来；最后是用深度搜索的方法遍历解空间树，同时根据需要采用剪枝函数，删去不可行结果和减少遍历时间，当遍历完，答案也就出来了。

最后

以上就是悲凉溪流最近收集整理的关于算法设计与分析第五章作业1. 请用回溯法的方法分析“最小重量机器设计问题”2. 你对回溯算法的理解的全部内容，更多相关算法设计与分析第五章作业1.内容请搜索靠谱客的其他文章。