1、算法分析与设计课程设计报告 目 录 一、问题描述 1 1、普通背包问题 1 2、0-1 背包问题 . 1 3、棋盘覆盖问题 1 二、问题分析 2 1、普通背包问题 2 2、0-1 背包问题 . 2 3、棋盘覆盖问题 3 三、算法设计 3 1、普通背包问题 3 2、0-1 背包问题 . 4 3、棋盘覆盖问题 4 四、算法实现 6 1、普通背包问题 6 2、0-1 背包问题 . 8 3、棋盘覆盖问题 10 五、测试分析 . 11 1、普通背包问题 .11 2、0-1 背包问题 . 13 3、棋盘覆盖问题 15 六、结论 . 16 七、源程序 . 17 1、普通背包问题 17 2、0-1 背包问题
2、. 20 3、棋盘覆盖问题 24 八、参考文献 . 26 算法分析与设计课程设计报告 - 1 - 一、问题描述一、问题描述 1 1、普通背包问题、普通背包问题 有一个背包容量为 C，输入 N 个物品，每个物品有重量 Si，以及物品放入 背包中所得的收益 Pi。求选择放入的物品，不超过背包的容量，且得到的收 益最好。物品可以拆分，利用贪心算法解决。 2 2、0 0- -1 1 背包问题背包问题 在 0/1 背包问题中，需对容量为 c 的背包进行装载。从 n 个物品中选取装入 背包的物品，每件物品 i 的重量为 wi, i, 价值为 pi i。对于可行的背包装载，背包 中的物品的总重量不能超过背包
3、的容量，最佳装载是指所装入的物品价值最高， 即 取得最大值。约束条件 =n) / i 表示深度（层） ，in 搜索到叶子节点 算法分析与设计课程设计报告 - 9 - bestp=cp; for(int j=0;j=tr+s else / 此棋盘中无特殊方格 boardtr+stc+s=t; / 用 t 号 L 型骨牌覆盖左上角 chessBoard(tr+s,tc+s,tr+s,tc+s,s); /覆盖其余方格 五五、测试分析、测试分析 1 1、普通背包问题、普通背包问题 1） 、输入物品个数 N=3,如图 6.1 所示。 图 6.1 输入物品数 2） 、输入背包容量 M：10，如图 6.2
4、所示。 算法分析与设计课程设计报告 - 12 - 图 6.2 输入背包容量 3） 、输入各物品的大小或重量 weight：6 、 5 、 5，如图 6.3 所示。 图 6.3 输入物品重量 4） 、输入各物品的价值 p：42、25、30，如图 6.4 所示。 图 6.4 输入物品价值 5） 、显示背包装载结果，如图 6.5 所示。 算法分析与设计课程设计报告 - 13 - 图 6.5 结果显示 2 2、0 0- -1 1 背包问题背包问题 1） 、输入背包容量：10,如图 6.6 所示。 图 6.6 输入背包容量 2） 、输入物品个数：3，如图 6.7 所示。 算法分析与设计课程设计报告 -
5、14 - 图 6.7 输入物品数量 3） 、输入各物品重量：6 、 5 、 5，如图 6.8 所示。 图 6.8 输入物品重量 4） 、输入各物品的价值：42、25、30，如图 6.9 所示。 图 6.9 输入物品价值 算法分析与设计课程设计报告 - 15 - 5） 、显示背包装载结果，如图 6.10 所示。 图 6.10 结果显示 3 3、棋盘覆盖问题、棋盘覆盖问题 1） 、输入 size：8，如图 6.11 所示。 图 6.11 输入棋盘大小 2） 、输入特殊方块的位置:4 3，如图 6.12 所示。 算法分析与设计课程设计报告 - 16 - 图 6.12 输入特殊方格位置 3）显示棋盘覆
6、盖结果，如图 6.13 所示。 图 6.13 结果显示 六六、结论、结论 三个算法，普通背包问题是用的贪心算法设计的，0-1 背包问题是用回溯算 法实现的，棋盘覆盖问题是用的分治法设计的。在开始设计时对贪心算法和分治 算法的思想很好理解，但是在设计算法时大概思路还是有的，但写完算法写代码 是发现写不出来，原因就是算法设计的还不够细，后来上网查了些资料，分析了 别人的算法，最终实现了现在的算法设计。 在最终完成的程序中：贪心算法求普通背包问题，基本上已经实现了主要的 功能；01 背包问题也能实现主要功能，但一开始未使用到界限函数，后来才加 上；在分治算法求棋盘覆盖问题时，也基本上实现了它的功能，但在输入时还有 算法分析与设计课程设计报告 - 17 - 不足，需要人工输入 2 的指数幂，不够方便。而且界面不够友好，不能实现单步 覆盖。 不过，总的来说这次实践也是有一定收获的，至少对书中这三个算法的知识 进行了巩固，自己更进一步地理解了这三个算法 贪心算
