DP|回溯七例

发表于 更新于 Valine： 本文字数： 12k 估计阅读时长 ≈ 11 分钟
问题背景1

设有n件工作分配给n个人。将工作i分配给第j个人所需要的费用为cij。试设计一个算法，为每个人分配1件不同的工作，并使总费用达到最小。

解题思路1

解空间

解空间为{x1,x2,x3,······,xn}，其中xi=1,2,3,4···,n，表示第i个人安排的工作号。

剪枝方法

算法中设置了一个数组，用来存放工作的完成状态，当工作完成时设为1，否则设为0。
代码实现1 
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
//c代码
#include<stdio.h>
#define n 3
int price[n][n] = {10,2,3,2,3,4,3,4,5};//费用 
int minprice = 10000;
int tempprice;
int a[n];//用于保存哪个人干了哪个工作
bool ok(int t){
 int i;
 for(i = 0;i < t;i ++){
  if(a[t] == a[i]){//表示出现同一个工作分配给了两个人 
   return false; 
  }
 }
 return true;
}
void nfs(int t){//t表示的是当前在为第t个人分配工作 
 int i;
 if(t == n){
  if(tempprice < minprice){
   minprice = tempprice;
  }
  return;
 } 
 for(i = 0;i < n;i ++){
  a[t] = i;
  tempprice += price[t][i];
  if(tempprice < minprice && ok(t)){
   nfs(t + 1); 
  }
  tempprice -= price[t][i];
 }
} 
int main()
{
 nfs(0);
 printf("%d\n",minprice); 
 return 0; 
} 
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
#include<iostream>
using namespace std;
#define N 1000
int cost[N][N];  // 表示第i个人完成第j件工作需要的费用
int isC[N] = {0}; // 用于记录第n个工作是否完成，0表示未完成
int n;
int scost;  // 表示总费用 
void Backstrack(int i, int c) 
 {
     if(c > scost) return;
     if(i == n) {  // 当最后一个人也分配好工作后判断总费用
         if(c < scost) scost=c;
         return;
     }
     for(int j=0;j<n;j++) {
         if(isC[j]==0) { // 判断第j个工作是否已经完成，类似剪枝函数
             isC[j]=1;
             Backstrack(i+1, c+cost[i][j]);
             isC[j]=0;  // 回溯法
         }
     }
 }

 int main()
 {
     cin>>n;
     for(int i=0;i<n;i++) {
         for(int j=0;j<n;j++) {
             cin>>cost[i][j];  
         }
     }
     scost = N;  // 给总费用设置一个很大的值
     Backstrack(0,0);  
         // 第一个0表示从第一个人开始 ，第二个0表示当前需要的总费用
     cout<<scost;
     return 0;
 }
问题背景2

现有n种不同形状的宝石，每种宝石有足够多颗。欲将这些宝石排列成m行n列的一个矩阵，m<=n，使矩阵中每一行和每一列的宝石都没有相同的形状。试设计一个算法，计算出对于给定的m和n，有多少种不同的宝石排列方案。

avatar
解题思路2

这个题目基本思想是 利用回溯法，对于 m 行 n 列， 本质上就是一个二维数组， 我们可以将问题的解写成 x[1],x[2],x[3] … x[m*n], 那么对于每个点 x[i] 的取值实际上是 [1, n], 套用回溯法的算法框架，这里的 约束条件 ，就是同行，同列 没有相同的取值， 并且这里没有优化目标，只要类似 N后问题找出所有解就可以了。

另外，回溯时候的边界条件，需要特别注意一下，由于我们把二维数组当作一维数组进行实现， 下标从 0 开始， 理论上到 m*n-1就应该结束了。
代码实现2 
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

#include<stdio.h>
#define m 3
#define n 3
int a[m][n];
int count = 0;
bool ok(int x,int y){
 int i;
 for(i = 0;i < x;i ++){
  if(a[i][y] == a[x][y]){
   return false;
  }
 }
 return true;
}
void nfs(int x,int y){//用xy表示走到第几行第几列了 
 int i;
 int temp;
 for(i = y;i < n;i ++){
  temp = a[x][y];
  a[x][y] = a[x][i];
  a[x][i] = temp;
  
  if(ok(x,y)){//因为每一行的数都是0~n-1,所以行上不会重复，只需要在列上判断每一列是否出现了相同的元素，有相同的则需要停止当前分支 
   if(x == m - 1){
    if(y == n - 1){
     count ++;
     return;
    }else{
     nfs(x,y + 1);
    }
   } else{
    if(y == n - 1){
     nfs(x + 1,0);
    }else{
     nfs(x,y + 1);
    }
   }
  }
  
  temp = a[x][y];
  a[x][y] = a[x][i];
  a[x][i] = temp; 
 }
}
int main()
{
 int i,j;
 for(i = 0;i < m;i ++){
  for(j = 0;j < n;j ++){
   a[i][j] = j + 1;
  }
 }
 nfs(0,0);
 printf("%d\n",count);
 return 0; 
}
问题背景3

话说大诗人李白，一生好饮。幸好他从不开车。一天，他提着酒壶，从家里出来，酒壶中有酒2斗。他边走边唱： 无事街上走，提壶去打酒。 逢店加一倍，遇花喝一斗。 这一路上，他一共遇到店5次，遇到花10次，已知最后一次遇到的是花，他正好把酒喝光了。 请你计算李白遇到店和花的次序，可以把遇店记为a，遇花记为b。则：babaabbabbabbbb 就是合理的次序。像这样的答案一共有多少呢？请你计算出所有可能方案的个数（包含题目给出的）。

解题思路3
已知最后一种情况，则只要填充前面14次即可。回溯的条件判断越严谨，效率越高，所以不要把所有的条件放在最后一次填充时判断。而是每次填充时，判断一下酒量和店，花的次数是否符合。
代码实现3 
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
//李白打酒（暴力） 
#include<stdio.h>
#include<math.h>
int main()
{
 int i,j,k;
 int num,temp;
 int flower,shop,wine;
 int count = 0;
 for(num = 0;num < pow(2,14);num ++){
  flower = 0;shop = 0;wine = 2;
  temp = num;
  for(i = 0;i < 14;i ++){
   if(temp % 2){
    flower ++;
    wine --;
   }else{
    shop ++;
    wine *= 2;
   }
   temp /= 2;
  }
  if(wine == 1 && flower == 9 && shop == 5){
   count ++;
  }
 } 
 printf("%d.\n",count);
 return 0; 
}
//李白打酒（回溯）
#include<stdio.h>
int count = 0;
int flower = 0;
int shop = 0;
int wine = 2;
void nfs(int n){
 if(n == 15){
  if(flower == 9 && shop == 5 && wine == 1){
   count ++;
  } 
  return;
 }
 if(flower <= 9 && shop <= 5){
  flower ++;
  wine --;
  nfs(n + 1);
  wine ++;
  flower --;
 }
 
 
 shop ++;
 wine *= 2;
 nfs(n + 1);
 wine /= 2;
 shop --;
}
int main()
{
 nfs(1); 
 printf("%d.\n",count);
 return 0; 
} 
//或是如下回溯
#include <stdio.h>
#include <math.h>
#include <string.h>
int a[14];
int count=0;
void backtrace(int t,int s,int f,int c){
 if(s>5 || f>9 || c<=0 )//剪枝 
     return;
 if(t==14){
  if(s==5 && f==9 && c==1)
   {
    count++;
    
   }
 
 return;
 }
 else{
  a[t]=1;//遇见酒店
  backtrace(t+1,s+1,f,c*2);
  a[t]=0;
 
  backtrace(t+1,s,f+1,c-1); 
  
 }
}
int main(){
 backtrace(0,0,0,2);
 printf("%d",count); 
 return 0;
}
问题背景4

假设某国家发行了n种不同面值的邮票，并且规定每张信封上最多只允许贴m张邮票。连续邮箱问题要求对于给定的n和m，给出邮票面值的最佳设计，在1张信封上贴出从邮资1开始，增量为1的最大连续邮资区间。 例如当n=5，m=4时，面值为1，3，11，15，32的5种邮票可以贴出邮资的最大连续区间是1到70。

解题思路4

每张信封最多贴m张邮票，也就是说可能贴了m张，也可能贴了0张、1张等等。为了便于计算，我们可以把未贴满m张邮票看作贴了x张邮票和m-x张面值为0的邮票，从而构造一棵完全多叉树。若求所有可能的组合情况，解空间是(n+1)^m。 以n=5,m=4为例，解空间为完全多叉树，图中只以一条路径为例：

实际求解需要对其进行剪枝：解的约束条件是必须满足当前解的邮资可以构成增量为1的连续空间，所以在搜索至树中任一节点时，先判断该节点对应的部分解是否满足约束条件，也就是判断该节点是否包含问题的最优解，如果肯定不包含，则跳过对以该节点为根的子树的搜索，返回上一层的节点，从其他子节点寻找通向最优解的路径；否则，进入以该节点为根的子树，继续按照深度优先策略搜索。 求解过程：

  1. 读入邮票面值数n，每张信封最多贴的邮票数m
  2. 读入邮票面值数组nums[]，除了正常面值，再加入一个值为0的面值
  3. 循环求取区间最大值maxValue，maxValue初始设为0 ① 从0张邮票开始搜索解空间，如果当前未达到叶节点，且过程值temp=temp+nums[i]未达到当前记录的区间最大值maxValue，则继续向下搜索 ② 若超过了区间最大值maxValue，则当前面值不是可行解，计算下一个面值nums[i+1]。若循环结束，当前节点的所有面值都无法满足，则说明再往下搜索也不可能有可行解，这个时候回溯到上一节点 ③ 若当前已搜索到叶节点，判断当前路径下的解temp是否满足比当前记录的区间最大值maxValue大1。若满足，则更新区间最大值maxValue；若不满足，回溯到上一节点
  4. 重复步骤3直到没有满足当前区间最大值maxValue+1的可行解，则当前记录的maxValue就是区间最大值
代码实现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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

//连续邮资问题
#include<stdio.h>
#define n 6
#define m 4
int a[n] = {0,1,3,11,15,32};//增加一个价格为0的邮票，这样就能利用回溯来解决问题，关键
int flag = 1;
int money;
int num; 
void nfs(int t){
 int i;
 if(flag == 0){
  return;
 }
 if(t == m){
  if(money == num)
   flag = 0;
  return;
 }
 for(i = 0;i < n;i ++){
  money += a[i];
  if(money <= num){
   nfs(t + 1);
  }
  money -= a[i];
 }
}
int main()
{
 num = 1;
 while(1){
  flag = 1;
  money = 0;
  nfs(0);
  if(flag)
   break;
  num ++;
 }
 printf("%d.\n",num - 1);
 return 0; 
}  
//2解法

#include <iostream>
#include <string.h>
 
using namespace std;
 
int n ,m ;     //邮票种类数，邮票允许的张帖数
int x[100];    //当前解
int bestx[100];//当前最优解
int y[10000];  //贴出各种邮资所需要的最少邮票数
int maxint;    //大整数
int maxl;      //邮资上界 
int maxvalue;  //当前最优值
 
 
void backTrace(int i ,int r)
{
 //递推求解任意邮资所需要的最少邮资数
 int z[10000];
 for(int j = 0 ; j <= x[i-2]*(m-1) ; j++)//这里是x-2
 {
  //如果小于最多邮资数
  if(y[j] < m)
  {
   for(int k = 1 ; k <= m - y[j] ; k++)
   {
    //更新邮资所需的最少张数
    if(y[j] + k < y[j + x[i-1] * k] )
    {
     y[j + x[i-1]* k ] = y[j] + k;
    }
   }
  }
 }
 //更新最大连续邮资值
 while(y[r] < maxint )
 {
  r++;
 }
 //判断是否搜索到最优解
 if(i > n)
 {
  //判断是否超过最优解
  if(r - 1 > maxvalue)//?r - 1
  {
   maxvalue = r - 1;
   //更新最优解
   for(int p = 1 ; p <= n ; p++)
   {
    bestx[p] = x[p];
   }
   return ;//易错，直接退出
  }
 }
 //拷贝邮资最少张数数组，用于回溯,对于每个x[i]的可能值进行赋值并求解
 for(int k = 1 ; k <= maxl; k++)
 {
  z[k] = y[k];
 }
 for(int j = x[i-1] + 1 ; j <= r ; j++)
 {
  x[i] = j ;
  backTrace( i+1 , r);//递归下一个编号
  //回溯
  for(int k = 1 ; k <= maxl; k++)
  {
   y[k] = z[k];
  }
 }
}
 
 
void process()
{ 
 while(cin >> n >> m)
 {
  maxint = 32767;
  maxl = 1500;
  maxvalue = 0;
  //初始化解
  memset(x , 0 , sizeof(x));
  //初始化邮资所需要的最少张数
  for(int i = 1 ; i <= maxl ; i++)
  {
   y[i] = maxint;
  }
  y[0] = 0;
  x[1] = 1;//第一个邮票面值必须为1
  backTrace(2,1);//第一个参数是邮票编号，第二个参数是最大连续邮资
  cout << maxvalue;
 
 }
}
 
int main(int argc,char* argv[])
{
 process();
 getchar();
 return 0;
}

问题背景5

还记得童话《卖火柴的小女孩》吗？现在，你知道小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。

输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。

示例 1:

输入: [1,1,2,2,2]

输出: true

解释: 能拼成一个边长为2的正方形，每边两根火柴。

示例 2:

输入: [3,3,3,3,4]

输出: false

解释: 不能用所有火柴拼成一个正方形。

解题思路5

新建立一个长为4的列表存储火柴，因为这里使用的是回溯，所以火柴按由大到小的顺序存储，这样可以减少回溯可能。在火柴全部存储后，就可以判断列表中四个小列表之和是否相等，如果都相等，证明可以拼成正方形。

在写代码的时候，先判断输入数组中火柴的总和是否为0，这是数组里火柴能否拼成正方形的先决条件。其次，在运行代码时，新建列表中的小列表之和不可超过总和长度的1/4。利用这些条件可以使代码的时间和空间复杂度很大程度的优化。
代码实现5 
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
#include<stdio.h>
#define n 8
#define m 4//正方形的四条边 
int len[n] = {1,8,3,7,5,4,3,5};
int sum[m] = {0};//用于保存每一条边上的木棍的长度的和 
int flag = 0;
int edge = 0;
bool ok(){
 int i;
 for(i = 0;i < m;i ++){
  if(sum[i] != edge){
   return false;
  }
 }
 return true;
}
void nfs(int t){
 int i;
 if(flag)
  return;
 if(t == n){
  if(ok()){
   flag = 1;
  }
  return;
 }
 for(i = 0;i < m;i ++){
  sum[i] += len[t];
  if(sum[i] <= edge){
   nfs(t + 1);
  }
  sum[i] -= len[t];
 } 
}
int main()
{
 int i;
 for(i = 0;i < n;i ++){
  edge += len[i];
 }
 if(edge % m != 0){
  printf("no.\n");
  return 0;
 }
 edge /= m;
 nfs(0);
 if(flag){
  printf("yes.\n");
 }else{
  printf("no.\n");
 }
 return 0; 
}
问题背景6

小明看完电影《第39级台阶》，离开电影院的时候，他数了数视觉的台阶数，恰好是39级。 ? 站在台阶前，他突然又想起一个问题：如果我每一步只能迈上1个或2个台阶，先迈左脚，然后左右交替，最后一步迈右脚，也就是说一共要迈偶数步。那么，上完39级台阶，有多少种不同的上法呢？ ? 请利用计算机的优势，帮助小明寻找答案。

解题思路6
递归回溯不断模拟1、2步上台阶的过程
代码实现6 
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
//39级台阶问题
#include<stdio.h>
int step = 0;
int foot = 0;
int count = 0;//统计方案 
void nfs(int step){
 if(foot % 2 == 0 && step == 39){
   count ++;
   return; 
 }
 //一步一个台阶
 foot ++;
 step ++;
 if(step <= 39)
  nfs(step);
 step --;
 foot --;
 //一步两个台阶 
 foot ++;
 step += 2;
 if(step <= 39)
  nfs(step);
 step -= 2;
 foot --; 
}
int main()
{
 nfs(0);
 printf("%d.\n",count);
 return 0;
}
//2解法
#include<stdio.h>
int step = 0;
int foot = 0;
int count = 0;//统计方案 
void nfs(){
 if(foot % 2 == 0 && step == 39){
   count ++;
   return; 
 }
 //一步一个台阶
 foot ++;
 step ++;
 if(step <= 39)
  nfs();
 step --;
 foot --;
 //一步两个台阶 
 foot ++;
 step += 2;
 if(step <= 39)
  nfs();
 step -= 2;
 foot --; 
}
int main()
{
 nfs();
 printf("%d.\n",count);
 return 0;
}
问题背景7

在nn的棋盘上放置彼此不受攻击的n个皇后，按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在nn格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。

解题思路7
  1. 针对给定问题，定义问题的解空间树
  2. 确定易于搜索的解空间结构
  3. 以深度优先方式搜索解空间，并且在搜索过程中永剪枝函数避免无效搜索。

下面给出一个三皇后问题的解空间树（3皇后问题无解），树中第i层的结点决定第i行皇后的摆放位置，均有三种不同的选择，便形成了三个孩子结点，但其中不包括不符合要求的布局。N皇后问题解空间树与三皇后问题解空间树类似。

代码实现7 
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
//n皇后问题 （暴力）
#include<stdio.h>
#include<math.h>
#define n 8 
int judge(int *a){
 int i,j;
 for(i = 0;i < n;i ++){
  for(j = i + 1;j < n;j ++){
   if(a[i] == a[j] || abs(i - j) == abs(a[i] - a[j])){
    return 0;
   }
  }
 }
 return 1;
}
int main()
{
 int i,j,k;
 int num;
 int temp;
 int a[n];
 int flag;
 int count = 0;
 for(num = 0;num < pow(n,n);num ++){
  temp = num;
  for(i = 0;i < n;i ++){
   a[i] = temp % n;
   temp /= n;
  }
  if(judge(a)){
   for(i = 0;i < n;i ++){
    printf("%d ",a[i]);
   }
   putchar('\n');
   count ++;
  }
 }
 printf("%d.\n",count);
 return 0; 
}
//n皇后问题 （回溯）
#include<stdio.h>
#include<math.h>
#define n 8
int count = 0;
int a[n];
int judge(int t){//t表示0~t这个区间上没有发生重复，也就是满足游戏规则 
 int i,j;
 for(i = 0;i <= t;i ++){
  for(j = i + 1;j <= t;j ++){
   if(a[i] == a[j] || abs(i - j) == abs(a[i] - a[j])){
    return 0;
   }
  }
 }
 return 1;
}
void nfs(int m){
 int i;
 if(m == n){
  count ++;
  return;
 }
 for(i = 0;i < n;i ++){
  a[m] = i;
  if(judge(m)){
   nfs(m + 1);
  }
 }
}
int main()
{
 nfs(0);
 printf("%d.\n",count);
 return 0; 
}
//回溯c++
#include <iostream>
#include<math.h>
using namespace std;
 
int Place(int k,int x[])
{
 for(int i=0;i<k;i++)
  if(x[i]==x[k] || abs(i-k)==abs(x[i]-x[k]))
   return 1;
 return 0;  
}
 
int Queen(int n,int x[],int sum)
{
 int k=0;
 int flag=0;//有无解标志 
 
 while (k>=0)
 {
  x[k]++;
 
  while(x[k]<n && Place(k,x)==1)
   x[k]++;
  if(x[k]<n && k==n-1)
  {
   flag=1;//有解 
   sum++; 
   for(int i=0;i<n;i++)
    cout<<x[i]+1<<"  ";
   cout<<endl;
   if(k<n && x[0]<n)
   {
    x[k--]=-1;//回溯 
    continue;
   }
   
  }
  if(x[k]<n && k<n-1)
   k+=1;
  else 
   x[k--]=-1;
  
 }
 if(flag==0)
 cout<<"无解。"<<endl; 
 return sum;
} 
 
int main()
{
 int sum=0;
 int n=8;//皇后个数
 int x[8];
 for(int i=0;i<n;i++)
  x[i]=-1;
 sum=Queen(n,x,sum);
 cout<<"解毕，共有 "<< sum <<" 个解。"<<endl;
 return 0;
}