背包问题，其烦覆盖算分设计与分析课程设计报告

课 程 设 计 报 告

课程设计名称：算法设计与分析 系 别： 学生姓名： 班 级： 学 号： 成 绩： 指导教师：

开课时间： 2012~2013 学年 1 学期

目 录

第一章 课程设计前言..................................................................................................... 3

1.1 课程设计目的 ..................................................................................................... 3 1.2 课程设计题目 ..................................................................................................... 3 第二章 普通背包问题 ...................................................................................................... 4

2.1 普通背包问题描述： ........................................................................................... 4 2.2普通背包问题分析 ............................................................................................... 4 2.3建立数学模型 ...................................................................................................... 4 2.4贪心算法解决普通背包问题： .............................................................................. 4

2.4.1 贪心算法介绍 ............................................................................................ 4 2.4.2 贪心法的基本思路 ..................................................................................... 5 2.4.3 贪心算法原理 ............................................................................................ 5 2.4.4 解决普通背包问题 ..................................................................................... 6 2.5算法实现 ............................................................................................................. 6 2.6测试分析 ............................................................................................................11

2.6.1 背包问题运行界面 ....................................................................................11 2.6.2 添加物品信息及背包载重 .........................................................................11 2.6.3修改物品信息界面.................................................................................... 12 2.6.4删除物品信息界面.................................................................................... 12 2.6.5 物品单价排序的界面 ............................................................................... 13 2.6.6 物品放入背包的重量：运行结果图 .......................................................... 13 2.6.7时间复杂度分析：.................................................................................... 14 2.7结论 .................................................................................................................. 14 第三章 棋盘覆盖问题................................................................................................... 15

3.1问题描述 ........................................................................................................... 15 3.2问题分析 ........................................................................................................... 15 3.3建立数学模型 .................................................................................................... 15 3.4分支算法解决棋盘覆盖问题 ............................................................................... 16

3.4.1分治算法的基本思路：............................................................................. 16 3.4.2分治算法解题步骤： ................................................................................ 16 3.4.3分治法解决棋盘覆盖问题：...................................................................... 16 3.5算法实现 ........................................................................................................... 18 3.6测试分析 ........................................................................................................... 22

3.6.1在DOS上输入棋盘大小及特殊方格位置界面： ........................................ 22 3.6.2 在DOS上显示棋盘覆盖情况：................................................................ 22

1

3.6.3 时间复杂度分析： ................................................................................... 22 3.7结论 .................................................................................................................. 22 第四章 参考文献 ........................................................................................................... 24

2

第一章 课程设计前言

1.1 课程设计目的

1．了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；

2．初步掌握软件开发过程的问题分析、算法设计、程序编码、测试等基本方法和技能；

3．提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 4．训练用系统的观点和软件开发一般规范进行软件开发。

1.2 课程设计题目

1、普通背包问题 要求：使用贪心算法实现；

2、棋盘覆盖问题

要求：使用分治算法实现；

3

第二章 普通背包问题

2.1 普通背包问题描述

已知n个物体重量为：w1、w2?n个物体价值为：p1、p2?背包载重为：M 物体i可以部分的装入背包，若物体i的一部分xi装入背包，则装入的重量为wi*xi，装入的价值为pi*xi；

最大物品放置的价值量。

2.2普通背包问题分析

第一，按单位物品价值递增将物品排序，放入相应的数组中，并对排序后的物品与已知物品重量相对应。便于最终计算。

第二，依次将单位价值大的物品放入背包（贪心选择），用总重量依次减去每次放入的重量，直到背包放满位置；即最终剩余重量为零。

第三，对于装入的物品不能全部放进去，则可以将部分物品放入背包；即放入的重量=剩余重量。

2.3建立数学模型

背包问题：

将n个物品按物品单价从大到小排列。 A{a1，a2，?，an} 约束条件： M=m1+m2+?+mn;

S=max(m1*a1+m2*a2+?+mn*an)。

2.4贪心算法解决普通背包问题：

2.4.1 贪心算法介绍

顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并

4

本文来源：https://www.bwwdw.com/article/bvtd.html