1.数字矩阵
任务目标：
给定一个N行M列的数字矩阵，从中选出若干个不相邻的数字(上下左右均不相邻），求他们的最大和为多少？
输入:
输入包括N+1行。
第一行包含两个整数N和M（0 < N,M<= 6），分别代表数字矩阵的长和宽。
接下来的N行每行有M个整数，为数字矩阵，每个数字不大于1000。
输出:
输出包括一行，包含一个整数，为选取数字最大的和。
输入样例1:
4 4
67 75 63 10
29 29 92 14
21 68 71 56
8 67 91 25
输出样例1:
429
输入样例2:
4 4
67 75 63 10
1 2 3 4
21 68 71 56
5 6 7 8
输出样例2:
266
具体代码：
#include <iostream>
using namespace std;
int n, m, a[25][25];
int ans, sum;
bool vis[25][25];
void dfs(int x, int y)
{
if (x == n + 1)
{
ans = max(ans, sum);
return;
}
int nx = x, ny = y + 1;
if (ny > m)
{
ny = 1;
nx = x + 1;
}
if (!vis[x - 1][y] && !vis[x][y - 1] && !vis[x][y + 1] && !vis[x + 1][y])
{
vis[x][y] = 1;
sum += a[x][y];
dfs(nx,ny);
vis[x][y] = 0;
sum -= a[x][y];
}
dfs(nx,ny);
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
dfs(1, 0);
cout << ans;
return 0;
}2.拓展延伸——过河
任务目标：
有n人要过河，每人体重分别为ci，船最大载重量为w，求最少需要几次才能全部过河？
输入:
输入包括两行。
第一行包含两个整数，n和w（n <= 15, 8 <= w <= 10）,分别代表需要运输的人数n和能负担的重量w。
第二行包含n个整数，为待运输的n个人的体重ci（ci <= 8）。
输出:
输出包括一行，包含一个整数，代表需要运输的次数。
输入样例1:
5 8 2 5 7 4 3
输出样例1:
3
输入样例2:
5 8 2 5 7 2 2
输出样例2:
3
具体代码：
#include <iostream>
using namespace std;
int w, n, c[20], tp[20], ans;
void dfs(int now, int cnt)
{
if(cnt==ans+1)
{
return;
}
if (now == n + 1)
{
ans = min(ans, cnt);
return;
}
for (int i = 1; i <= cnt; i++)
{
if (tp[i] + c[now] <= w)
{
tp[i] += c[now];
dfs(now + 1, cnt);
tp[i] -= c[now];
}
}
tp[cnt + 1] = c[now];
dfs(now + 1, cnt + 1);
tp[cnt + 1] = 0;
}
int main()
{
cin >> n >> w;
for (int i = 1; i <= n; i++)
cin >> c[i];
ans = n;
dfs(1, 0);
cout << ans << endl;
return 0;
}