1.子集和问题
题目描述：
子集和问题的一个实例为〈S,t〉。其中，S={ x1 ， x2 ，…，xn }是一个正整数的集合，c是一个正整数。子集和问题判定是否存在S的一个子集S1，使得：
试设计一个解子集和问题的回溯法。
对于给定的正整数的集合S={ x1 ， x2 ，…，xn }和正整数c，计算S 的一个子集S1，使得：
输入格式：
输入数据的第1 行有2 个正整数n 和c（n≤10000，c≤10000000），n 表示S 的大小，c是子集和的目标值。接下来的1 行中，有n个正整数，表示集合S中的元素。
输出格式：
将子集和问题的解输出。当问题无解时，输出“No Solution!”。
样例
输入
5 10
2 2 6 5 4
输出
2 2 6
此代码非自写，摘自https://fangkaipeng.com/（C++）
#include <bits/stdc++.h>
using namespace std;
int n, c;
int ans[10005], a[10005], m, f;
void dfs(int i, int sum, int pos) {
if (sum > c || f == 1) return;
if (sum == c) {
f = 1;
for (int i = 0; i < pos; i++) printf("%d%c", ans[i], i == pos - 1 ? '\n' : ' ');
return;
}
for (; i < n; i++) {
if (a[i] + sum <= c) {
ans[pos] = a[i];
dfs(i + 1, sum + a[i], pos + 1);
}
}
}
int main() {
cin >> n >> c;
int sum = 0;
for (int i = 0; i < n; i++) scanf("%d", a + i), sum += a[i];
if (sum < c) cout << "No Solution!";
else {
dfs(0, 0, 0);
if (!f) cout << "No Solution!";
}
return 0;
}
2.运动员最佳匹配问题
题目描述：
羽毛球队有男女运动员各n 人。给定2 个n×n 矩阵P 和Q。P[i][j]是男运动员i 和女运动员j配对组成混合双打的男运动员竞赛优势；Q[i][j]是女运动员i和男运动员j配合的女运动员竞赛优势。由于技术配合和心理状态等各种因素影响，P[i][j]不一定等于Q[j][i]。男运动员i和女运动员j配对组成混合双打的男女双方竞赛优势为P[i][j]*Q[j][i]。
设计一个算法，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。
设计一个算法，对于给定的男女运动员竞赛优势，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。
输入格式：
输入数据的第一行有1 个正整数n (1≤n≤20)。接下来的2n 行，每行n个数。前n行是p，后n行是q。
输出格式：
将计算出的男女双方竞赛优势的总和的最大值输出。
样例
输入
3
10 2 3
2 3 4
3 4 5
2 2 2
3 5 3
4 5 1
输出
52
此代码非自写，摘自https://fangkaipeng.com/（C++）
#include <bits/stdtr1c++.h>
using namespace std;
int ans, vis[111], sum;
int n;
int p[111][111], q[111][111], a[111];
void dfs(int i) {
if (i == n) {
ans = max(ans, sum);
return;
}
int temp = 0;
for (int j = i; j < n; j++) {
temp += a[j];
}
if (sum + temp <= ans) return;
for (int j = 0; j < n; j++) {
if (vis[j] == 0) {
vis[j] = 1;
sum += p[i][j] * q[j][i];
dfs(i + 1);
sum -= p[i][j] * q[j][i];
vis[j] = 0;
}
}
}
int main() {
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
cin >> p[i][j];
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) cin >> q[i][j];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) a[i] = max(a[i], p[i][j] * q[j][i]);
dfs(0);
cout << ans;
return 0;
}
3.工作分配问题
题目描述：
设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为 cij。试设计一个算法，为每一个人都分配1 件不同的工作，并使总费用达到最小。
设计一个算法，对于给定的工作费用，计算最佳工作分配方案，使总费用达到最小。
输入格式：
输入数据的第一行有1 个正整数n (1≤n≤11)。接下来的n行，每行n个数，表示工作费用。
输出格式：
将计算出的最小总费用输出。
样例
输入
3
10 2 3
2 3 4
3 4 5
输出
9
代码一（C++，暴力）：
#include <bits/stdtr1c++.h>
using namespace std;
int main() {
int n;
scanf("%d", &n);
vector<vector<int>> v1(n, vector<int>(n));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%d", &v1[i][j]);
vector<int> v2(n);
iota(v2.begin(), v2.end(), 0);
int sum1 = 0x3f3f3f3f;
do {
int sum2 = 0;
for (int i = 0; i < n; i++)
sum2 += v1[i][v2[i]];
sum1 = min(sum1, sum2);
} while (next_permutation(v2.begin(), v2.end()));
printf("%d", sum1);
return 0;
}
代码二（Python，搜索）：
def dfs(r, s):
global lim
if s > lim:
return
if r == n:
lim = min(lim, s)
for i in range(n):
if vis[i] == 0:
vis[i] = 1
dfs(r + 1, s + a[r][i])
vis[i] = 0
n = int(input())
a, vis, lim = [], [0] * 25, 1e7
for i in range(n):
a.append(list(map(int, input().split())))
dfs(0, 0)
print(lim)
4.整数变换问题
题目描述：
整数变换问题。关于整数i的变换f和g定义如下：f(i)=3i；
试设计一个算法，对于给定的2 个整数n和m，用最少的f和g变换次数将n变换为m。例如，可以将整数15用4 次变换将它变换为整数4：4=gfgg(15)。当整数n不可能变换为整数m时，算法应如何处理?
对任意给定的整数n和m，计算将整数n变换为整数m所需要的最少变换次数。
输入格式：
输入数据的第一行有2 个正整数n和m。n≤100000，m≤1000000000。
输出格式：
将计算出的最少变换次数以及相应的变换序列输出。第一行是最少变换次数。第2 行是相应的变换序列。
样例
输入：
15 4
输出：
4
gfgg
代码（C++）：
#include <bits/stdtr1c++.h>
using namespace std;
int n, m, cnt = 1;
string s = "";
int dfs(int n, int cur) {
if (cur > cnt) return 0;
int sum = n;
for (int i = 0; i < 2; i++) {
sum = (i == 0 ? n * 3 : n / 2);
if (sum == m || dfs(sum, cur + 1)) {
s += (i == 0 ? 'f' : 'g');
return 1;
}
}
return 0;
}
int main() {
cin >> n >> m;
while (!dfs(n, 1)) {
cnt++;
}
cout << cnt << endl << s;
return 0;
}