庞志永-算法分析-课程设计报告2

数据结构与算法分析2课程设计报告书班级学号姓名指导教师庞志永课程设计项目名称：背包问题的多项式时间近似方案1.问题描述：背包问题可描述为如下的整数规划形式，其中M为背包的容量，P为物体的价值，W为物体的体积。2.基本要求：(1)在给定参数K的条件下，设计背包问题的满足近似性能比不大于1+1/(k+1)的多项式时间近似方案，并选择适当的编程语言在计算机上实现。(2)程序能够正常运行，计算结果正确，满足设计要求。3.算法描述：将装入背包的物体进行多次尝试，其方法是：取K为确定的非负整数，考虑背包问题的实例I中的n个物体的合的K元素子集C，|C|=K。(1)尝试将每个K元素子集C中的物体优先装入背包；(2)利用解答背包问题的贪心算法A将(n-K)个物体尝试装入背包。合并先装入的K个物体和用算法A装入的剩余物体作为算法的最终解。过程如下：Procedure-APPROX(P,W,M,n,K)(1)PMAX=0;(2)ForallcombinationsCofsize=K&weight≤Mdo(3)PC=i∈CPi(4)PMAX=max{PMAX,PC+L(I,P,W,M,n)};(5)Endfor(6)End-APPROXProcedureL(I,P,W,M,n)(1)S1=0;T=M－i∈CWi;(2)Fori=1tondo(3)IfiCandWi≤Tthen(4)S1=S1+Pi,T=T–Wi(5)Endif(6)Endfor(7)S=max{S1,max{Pi|iC}};(8)Return(S)(9)EndL4.模块划分(仅供参考)：(1)输入及存储原始数据模块(2)-APPROX(P,W,M,n,K)模块(3)L(I,P,W,M,n)模块(4)存储及输出结果模块11max{0,1},1niiiiniiiPxxinWxM5.本课程设计中遇到的关键问题及其解决方法：6.运行结果及其相关描述：要求实例中物体的数量在20—100之间。7.其他需要说明的问题：8.课程设计总结：附录：相关模块代码及其描述：