分书问题与上一篇文章中的“”几乎是一样的，只不过在变成写代码求解时用到的数据结构比 N 皇后问题简单了许多，或许这个分书问题更能让人明白回溯法的使用情况。

分书问题：有编号为 A、B、C、D、E 的 5 本书，以及 5 个人，每本书可以分给每一个对该书有兴趣的人阅读，且每个人都只能分到一本自己感兴趣的书。问当给定 5 个人对 5 本书的感兴趣情况时，怎样分配这 5 本书才能让每个人都开始阅读。

思路：与 N 皇后问题几乎一致，每次都尝试给第 p 个人从 5 本书中分出他感兴趣的一本，若不能构成最终解，则撤销回溯到上一个人（即第 p – 1 个人）的分配。但是所需数据结构有所不同，我们如下确定：

int bookCounts 表示书的总数量，与总人数相等

int like [p] [b] = 1 表示第 p 个人喜欢读第 b 本书，即具体的问题初始条件；

int given [b] = p 表示第 b 本书分给了第 p 个人，即保存解的标识数组；

注：在这里 p ，b （即下标）都从 0 开始，这与上篇文章中的 N 皇后问题不同，N 皇后问题是为了数据处理更加直观些，而这里分数问题比较简单。

基于这种数据结构，算法实现如下：

1. /**  
2.  * 回溯法求解分书问题  
3.  * @author haolloyin  
4.  */ 
5. public class AllacateBooks {  
6.  
7.     // 书的总数量，与总人数相等  
8.     private int bookCounts = 5;  
9.  
10.     // like[p][b] 表示第 p 个人喜欢读第 b 本书  
11.     private int[][] like = new int[bookCounts][bookCounts];  
12.  
13.     // given[b] = p 表示将第 b 本书分配给第 p 个人  
14.     private int[] given = new int[bookCounts];  
15.  
16.     // 初始化标识数组 given[] 和传入各人喜欢书的情况数组  
17.     private void init(int like[][]) {  
18.         for (int i = 0; i < bookCounts; i++) {  
19.             given[i] = -1; // -1 表示第 i 本书还没分配出去  
20.         }  
21.         this.like = like;  
22.     }  
23.  
24.     // 尝试给每一个人分配一本书  
25.     public void allocateBook(int person) {  
26.         for (int bookNum = 0; bookNum < bookCounts; bookNum++) {  
27.  
28.             if (like[person][bookNum] == 1 && given[bookNum] == -1) {  
29.                 given[bookNum] = person;  
30.  
31.                 if (person == bookCounts - 1) {  
32.                     // 打印结果  
33.                     for (int i = 0; i < bookCounts; i++) {  
34.                         System.out.println("人 " + (given[i]+1) + " <---> 书 " 
35.                                 + ((char)(i + 'A')));  
36.                     }  
37.                     System.out.println();  
38.                 } else {  
39.                     // 为下一个人分配一本书  
40.                     allocateBook(person + 1);  
41.                 }  
42.                 // 失败，回溯重新寻找解  
43.                 given[bookNum] = -1;  
44.             }  
45.         }  
46.     }  
47.  
48.     // 测试  
49.     public static void main(String[] args) {  
50.         // 构造一个问题规模  
51.         int[][] like = new int[][]{   
52.                 { 0, 0, 1, 1, 0 },   
53.                 { 1, 1, 0, 0, 1 },  
54.                 { 0, 1, 1, 0, 1 },  
55.                 { 0, 0, 0, 1, 0 },   
56.                 { 0, 1, 0, 0, 1 }};  
57.  
58.         AllacateBooks allocateBooks = new AllacateBooks();  
59.         allocateBooks.init(like);  
60.         allocateBooks.allocateBook(0);  
61.     }  
62. } 

对应于所给的问题规模，所得的解如下：

人 2 <---> 书 A人 3 <---> 书 B人 1 <---> 书 C人 4 <---> 书 D人 5 <---> 书 E人 2 <---> 书 A人 5 <---> 书 B人 1 <---> 书 C人 4 <---> 书 D人 3 <---> 书 E

小结：

比较重要的还是根据问题选择、设计有利于解决问题、实现算法的数据结构。

本文转自 xxxx66yyyy 51CTO博客，原文链接：http://blog.51cto.com/haolloyin/353200，如需转载请自行联系原作者