青岛科技大学算法设计与分析实验报告 算法实训 背包问题.pdf

数据结构与算法分析 2 课程设计报告书 班级 学号 姓名 指导教师 庞志永 课程设计项目名称 背包问题的多项式时间近似方案 1.问题描述 背包问题可描述为如下的整数规划形式其中 M为背包的容量 P为物体的价值 W为物体 的体积 n max Px i 1 i i xi {0,1}, 1 i n n W x M i 1 i i 2.基本要求 (1) 在给定参数 K 的条件下 设计背包问题的满足近似性