算法设计与分析实验报告
学院：信息学院
专业：物联网1101
姓名：黄振亮 学号：20113379
2013年11月
目录
作业1 0-1背包问题的动态规划算法 ...................................................... 7 1.1算法应用背景 ................................................................................ 3 1.2算法原理 ........................................................................................ 3 1.3算法描述 ........................................................................................ 4 1.4程序实现及程序截图 .................................................................... 4 1.4.1程序源码 ............................................................................... 4 1.4.2程序截图 ............................................................................... 5 1.5学习或程序调试心得 .................................................................... 6 作业2 0-1背包问题的回溯算法 .............................................................. 7 2.1算法应用背景 ................................................................................ 3 2.2算法原理 ........................................................................................ 3 2.3算法描述 ........................................................................................ 4 2.4程序实现及程序截图 .................................................................... 4 2.4.1程序源码 ............................................................................... 4 2.4.2程序截图 ............................................................................... 5 2.5学习或程序调试心得 .................................................................... 6 作业3循环赛日程表的分治算法 ............................................................ 7 3.1算法应用背景 ................................................................................ 3 3.2算法原理 ........................................................................................ 3 3.3算法描述 ........................................................................................ 4 3.4程序实现及程序截图 .................................................................... 4
1
3.4.1程序源码 ............................................................................... 4 3.4.2程序截图 ............................................................................... 5 3.5学习或程序调试心得 .................................................................... 6 作业4活动安排的贪心算法 .................................................................... 7 4.1算法应用背景 ................................................................................ 3 4.2算法原理 ........................................................................................ 3 4.3算法描述 ........................................................................................ 4 4.4程序实现及程序截图 .................................................................... 4 4.4.1程序源码 ............................................................................... 4 4.4.2程序截图 ............................................................................... 5 4.5学习或程序调试心得 .................................................................... 6
2
作业1 0-1背包问题的动态规划算法
1.1算法应用背景
从计算复杂性来看,背包问题是一个NP难解问题。半个世纪以来,该问题一直是算法与复杂性研究的热点之一。另外,背包问题在信息加密、预算控制、项目选择、材料切割、货物装载、网络信息安全等应用中具有重要的价值。如果能够解决这个问题那么则具有很高的经济价值和决策价值，在上述领域可以获得最大的价值。本文从动态规划角度给出一种解决背包问题的算法。
1.2算法原理
1.2.1、问题描述：
给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
形式化描述：给定c >0, wi >0, vi >0 , 1≤i≤n.要求找一n元向量(x1,x2,…,xn,), xi∈{0,1}, ? ∑ wi xi≤c,且∑ vi xi达最大.即一个特殊的整数规划问题。
1.2.2、最优性原理：
设(y1,y2,…,yn)是 (3.4.1)的一个最优解.则(y2,…,yn)是下面相应子问题的一个最优解:
证明:使用反证法。若不然,设(z2,z3,…,zn)是上述子问题的一个最优解,而(y2,y3,…,yn)不是它的最优解。显然有
∑vizi > ∑viyi (i=2,…,n) 且 w1y1+ ∑wizi<= c
因此 v1y1+ ∑vizi (i=2,…,n) > ∑ viyi, (i=1,…,n)
说明(y1,z2, z3,…,zn)是(3.4.1)0-1背包问题的一个更优解,导出(y1,y2,…,yn)不是背包问题的最优解,矛盾。
1.2.3、递推关系： 3