1、的物品中选取，如此重复，直至求得满足条件的解。 因为回溯求解的规则是后进先出，所以要用到栈来存储符合条件的解，在存储过程中，利用数组来存储各个物品的体积，然后用深度优先的搜索方式求解，将符合条件的数组元素的下标存入栈里，最后得到符合条件的解并且实现输出。将2k x 2k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格三个子棋盘，将他们中的也假一个方格设为特殊方格。如果是：左上的子棋盘（若不存在特殊方格）则将该子棋盘右下角的那个方格假设为特殊方格；右上的子棋盘（若不存在特殊方格）则将该子棋盘左下角的那个方格假设为特殊方格；左下的子棋盘（若不存在特殊方格）则将该子棋
2、盘右上角的那个方格假设为特殊方格；右下的子棋盘（若不存在特殊方格）则将该子棋盘左上角的那个方格假设为特殊方格。当然上面四种，只可能且必定只有三个成立，那三个假设的特殊方格刚好构成一个L型骨架，我们可以给它们作上相同的标记。这样四个子棋盘就分别都和原来的大棋盘类似，我们就可以用递归算法解决。三、算法设计1）基本思路：首先，按物品单位价值由大到小将物品排序；（为了贪心选择准备）然后，依次将单位价值大的物品放入背包（贪心选择），直到背包放满为止；在向背包放置物品的过程中，如果正在考虑装入的物品不能全部放进去，则可以将物品的部分放入背包；2）算法设计：用一维数组xn （xi1,2, ,n），保存问题的
3、解；weight存储物品重量; price存储物品价值。 确定问题的解空间，并将解空间组织成易于搜索的子集树的形式；图4.1解空间树以深度优先的方式搜索整个解空间，遇到不满足约束要求的节点就回溯，沿另一个分支继续搜索；约束函数剪枝，不能超载，超载就回溯。1）问题分解过程如下： 以k=2时的问题为例，用二分法进行分解，得到的是如下图4-8，用双线划分的四个k=1的棋盘。但要注意这四个棋盘，并不都是与原问题相似且独立的子问题。因为当如图4-8中的残缺方格在左上部时，第1个子问题与原问题相似，而右上角、左下角和右下角三个子棋盘（也就是图中标识为2、3、4号子棋盘），并不是原问题的相似子问题，自然也就
4、不能独立求解了。当使用一个号三格板（图中阴影）覆盖2、3、4号三个子棋盘的各一个方格后，如4-8右图所示，我们把覆盖后的方格，也看作是残缺方格（称为“伪”残缺方格），这时的2、3、4号子问题就是独立且与原问题相似的子问题了。图4.2 图4.3从以上例子还可以发现，当残缺方格在第1个子棋盘，用号三格板覆盖其余三个子棋盘的交界方格，可以使另外三个子棋盘转化为独立子问题；同样地（如下图4-9所示），当残缺方格在第2个子棋盘时，则首先用号三格板进行棋盘覆盖，当残缺方格在第3个子棋盘时，则首先用号三格板进行棋盘覆盖，当残缺方格在第4个子棋盘时，则首先用号三格板进行棋盘覆盖，这样就使另外三个子棋盘转化为独
5、立子问题。如下图4.4所示：图4.42）棋盘的识别： 棋盘的规模是一个必要的信息，有了这个信息，只要知道其左上角的左上角方格所在行、列就可以唯一确定一个棋盘了，残缺方格或“伪”残缺方格直接用行、列号记录。 tr 棋盘中左上角方格所在行。 tc 棋盘中左上角方格所在列。 dr 残缺方块所在行。 dl 残缺方块所在列。 size:棋盘的行数或列数3）数据结构设计：用二维数组board ，模拟棋盘。覆盖残缺棋盘所需要的三格板（L牌）数目为：（ size2 -1 ） / 3；将这些三格板编号为1到（ s i z e2-1 ） / 3。则将残缺棋盘三格板编号的存储在数组board 的对应位置中，这样输出
6、数组内容就是问题的解。结合图4.4，理解算法。四、算法实现1）声明变量、函数/ 声明变量int N; /物品数量int M; /背包容量double XMAX; /背包问题最优解double WeightMAX; /物品重量 double PriceMAX; /物品价值double unit_priceMAX; /物品单位价值double total_price; /背包总价值 /声明函数void Input（）; /输入函数void Mergesort（）; /排序void knapsack（）; /背包装载int Output（）; /结果输出。2）实现了按照价值密度的降序排列void M
7、ergesort（） double temp1,temp2,temp3; for（int i=1;iN;i+） for（int j=1;j=N-i;j+） if（unit_pricejunit_pricej+1） temp1=Pricej;Pricej=Pricej+1;Pricej+1=temp1; temp2=Weightj;Weightj=Weightj+1;Weightj+1=temp2; temp3=unit_pricej;unit_pricej=unit_pricej+1;unit_pricej+1=temp3; 3）求最大总价值void knapsack（） for（ int i
8、=1;=N; i+ ） /初始化Xi，所有物品没有放入背包 unit_pricei=Pricei/Weighti; /计算物品单位价值unit_price X i=0; double left=M; /背包剩余载重 Mergesort（）; /按单位价值将物品排序，便于贪心选择 while（left!=0） for（int i=1;i+） /贪心选择，总是选择价值最大放入背包 if（Weightileft） /部分放入背包 Xi=left/Weighti; left=0; total_price=total_price+Pricei*Xi;#define N 100 /最大物品数/声明变量do
9、uble c;int n; /物品数double wN; /物品重量数组double pN; /物品价值数组double cw; /当前重量double cp; /当前价值double bestp; /当前最优价值int pathN; /当前最优路径int xN; /最佳装载/声明结构体Goodsstruct Goods double weight; /物品重量 double price; /总价值 int id; /物品编号 float unit_price;Goods goodsN=0,0,0,0;void backtract（int i）; /搜索解空间函数double bound（in
10、t i）; /界限函数void Output（）; /输出函数2） 搜索解空间函数/=搜索解空间=void backtract（int i） /到达叶节点 if（i=n） / i表示深度（层），in搜索到叶子节点 bestp=cp; for（int j=0;n; xj=pathj; return; /搜索子树 if（cw+wibestp） /当前的节点不合适时，跳到下一个结点 pathi=0;3）界限函数：/= 限界函数,计算当前价值与剩余价值和=double bound（int i） double cleft=c-cw; / 剩余容量 double bound=cp; / 当前物品价值 /以
11、物品单位重量价值递减的顺序装入物品 while（i=n&wi cleft 跳出循环，背包装满,物品部分装入背包 /装满背包 if（i=n） bound+=pi*cleft/wi; return bound; / 当前物品价值与剩余物品价值之和1）声明变量：int title=1; /L型骨牌号int board6464; /二维数组board ，模拟棋盘/*tr 棋盘中左上角方格所在行。tc 棋盘中左上角方格所在列。dr 残缺方块所在行。dl 残缺方块所在列。size:*/2）棋盘覆盖分治实现：void chessBoard（int tr,int tc,int dr,int dc,int si
12、ze） int s,t; if（size=1） return; /size:棋盘行数 t=title+; s=size/2; / 分割棋盘 / 覆盖左上角子棋盘 if（drtr+s & dc=tc+s） /特殊方格在此棋盘中 chessBoard（tr,tc+s,dr,dc,s）; boardtr+s-1tc+s=t; / 用 t 号L型骨牌覆盖左下角 chessBoard（tr,tc+s,tr+s-1,tc+s,s）; / 覆盖左下角子棋盘 if（dr=tr+s & chessBoard（tr+s,tc,dr,dc,s）; else / 此棋盘中无特殊方格 boardtr+stc+s-1=t
13、; /用 t 号L型骨牌覆盖右上角 chessBoard（tr+s,tc,tr+s,tc+s-1,s）; /覆盖其余方格 /覆盖右下角子棋盘=tc+s） /特殊方格在此棋盘中 chessBoard（tr+s,tc+s,dr,dc,s）; boardtr+stc+s=t; / 用 t 号L型骨牌覆盖左上角 chessBoard（tr+s,tc+s,tr+s,tc+s,s）;五、测试分析1）、输入物品个数N=3,如图6.1所示。图6.1输入物品数2）、输入背包容量M：10，如图6.2所示。图6.2输入背包容量3）、输入各物品的大小或重量weight：6 、 5 、 5，如图6.3所示。图6.3输入
14、物品重量4）、输入各物品的价值p：42、25、30，如图6.4所示。图6.4输入物品价值5）、显示背包装载结果，如图6.5所示。图6.5结果显示1）、输入背包容量：10,如图6.6所示。图6.6输入背包容量2）、输入物品个数：3，如图6.7所示。图6.7输入物品数量3）、输入各物品重量：6 、 5 、 5，如图6.8所示。图6.8输入物品重量4）、输入各物品的价值：42、25、30，如图6.9所示。图6.9输入物品价值5）、显示背包装载结果，如图6.10所示。图6.10结果显示1）、输入size：8，如图6.11所示。图6.11输入棋盘大小2）、输入特殊方块的位置:4 3，如图6.12所示。图
15、6.12输入特殊方格位置3）显示棋盘覆盖结果，如图6.13所示。图6.13结果显示六、结论三个算法，普通背包问题是用的贪心算法设计的，0-1背包问题是用回溯算法实现的，棋盘覆盖问题是用的分治法设计的。在开始设计时对贪心算法和分治算法的思想很好理解，但是在设计算法时大概思路还是有的，但写完算法写代码是发现写不出来，原因就是算法设计的还不够细，后来上网查了些资料，分析了别人的算法，最终实现了现在的算法设计。在最终完成的程序中：贪心算法求普通背包问题，基本上已经实现了主要的功能；01背包问题也能实现主要功能，但一开始未使用到界限函数，后来才加上；在分治算法求棋盘覆盖问题时，也基本上实现了它的功能，但
16、在输入时还有不足，需要人工输入2的指数幂，不够方便。而且界面不够友好，不能实现单步覆盖。不过，总的来说这次实践也是有一定收获的，至少对书中这三个算法的知识进行了巩固，自己更进一步地理解了这三个算法贪心算法：从问题的初始解出发逐步逼近给定的目标，每一步都做出当前看来是最优的选择（贪心选择），最终得到整个问题的最优解。就是一种穷举搜索算法。通俗地讲：回溯法是一种“能进则进，进不了则换，换不了则退”的基本搜索方法。在0-1背包问题中，为了提高搜索效率，避免一些无效的搜索，则需要用限界函数bound（）剪去得不到最优解的子树。分治法：分而治之。即将一个难以直接解决的大问题小规模化，待解出子问题解之后，
17、将子问题解合并为该问题解。七、源程序#include#define MAX 100 /物品件数最大值 /结果输出/=输入函数=void Input（） int i; coutendl;请输入背包总容量M:M;请输入各物体的大小或重量weight: for（i=1;Weighti;请输入各物体的价值price:Pricei;/=按照价值密度的降序排列=/=实现背包装载= i+ ） /初始化Xi，所有物品没有放入背包 unit_pricei=Pricei/Weighti; /计算物品单位价值unit_price /按单位价值将物品排序，便于贪心选择i+） /贪心选择，总是选择价值最大放入背包/=结果输出=int Output（） char ch; cout贪心算法实现背包装载结果为:i+） cout第个物体大小: Weighti 物体价值: Pricei 物体价值密度: unit_pricei 向量表示: （ i+） /输出背包问题最优解Xi ）背包的最优装载值为：total_price /背包所装载总价值 按Y或y继续操作，否则按任意键
