1.你对回溯算法的理解
回溯算法就是一种有组织的系统最优化搜索技术，可以看作蛮力法穷举搜索的改进。它的实质就是在问题的解空间进行深度优先搜索。回溯法常常可以避免搜索所有可能的解，所以它适用于求解组织数量较大的问题。
回溯法的一般步骤：
（1）.针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解。
（2）.确定易于搜索的解空间结构，使得能用回溯法方便地搜索整个解空间。
（3）.以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。
（1）子集树：但所有的问题是从n个元素的集合中找出满足某种性质的子集时，相应的解空间树成为子集树
（2）排列树：当所给出问题是确定n个元素满足某种性质的排列时，相应的解空间称为排列树。
剪枝函数（避免无效搜索）：
（1）用约束条件剪除得不到的可行解的子树
（2）用目标函数剪取得不到的最优解的子树
回溯法的优点在于其结构明确，可读性强，易于理解，而且通过对问题的分析可以大大提高运行效率。
2.请说明“子集和”问题的解空间结构和约束函数
7-1 子集和问题 （50 分）
设集合S={x1,x2,…,xn}是一个正整数集合，c是一个正整数，子集和问题判定是否存在S的一个子集S1，使S1中的元素之和为c。试设计一个解子集和问题的回溯法。
输入格式:
输入数据第1行有2个正整数n和c，n表示S的大小，c是子集和的目标值。接下来的1行中，有n个正整数，表示集合S中的元素。 是子集和的目标值。接下来的1 行中，有n个正整数，表示集合S中的元素。
输出格式:
输出子集和问题的解，以空格分隔，最后一个输出的后面有空格。当问题无解时，输出“No Solution!”。
输入样例:
在这里给出一组输入。例如：
5 10
2 2 6 5 4
输出样例:
在这里给出相应的输出。例如：
2 2 6
解空间结构：
约束函数：
用rest来表示从当前元素加到最后一个元素的总和，用来回溯时判断限界剪枝
当sum + rest >= c，即当前所选元素之和+从当前元素加到最后一个元素的总和>=目标值时，走右子树。
#代码
// // main.cpp // 123 // // Created by 王子涵 on 2017/12/5. // Copyright © 2017年 王子涵. All rights reserved. // // ConsoleApplication1.cpp : 定义控制台应用程序的入口点。 // #include<iostream> using namespace std; #define N 10000 int n, c, rest = 0; int a[N]; int x[N] = {0}; int sum = 0; bool backtrack(int t) { if( sum == c ) return true; if( t > n ) return false ; rest-=a[t]; if(sum + a[t] <= c) { x[t] = 1 ; sum = sum+a[t] ; if ( backtrack(t+1) ) return true; sum -= a[t]; } if( sum + rest >= c) { x[t] = 0 ; if ( backtrack(t+1) ) return true; } rest += a[t]; return false; } int main() { cin >>n>>c; for (int i = 1; i <= n; i++) { cin >> a[i]; rest += a[i]; } if (!backtrack(1)) cout << "No Solution!"; else for( int i = 1; i <= n; i++) if ( x[i] ) cout << a[i] << " "; cout << endl; return 0; }
3.请说明在本章学习过程中遇到的问题及结对编程的情况
本章学习过程中遇到的问题是如何构造解空间树以及进行剪枝，前者关乎解题思路，剪枝方法关乎效率。结对编程讨论加快了我们对解空间树的构造，同时也能很快的确定剪枝方法，加快了做题效率。