背包（动态规划回溯）和背包（贪心）实验报告(共12页).doc

精选优质文档-倾情为你奉上西安郵電學院算法设计与分析课内试验报告题 目：0-1背包(动态规划、回溯)和背包(贪心)院系名称： 计算机学院 专业名称： 软件工程专业班 级： 0903班 学生姓名： 张桥学号（8位）： (23)指导教师： 陈琳时间：2011年12月专心-专注-专业一. 设计目的通过上机实验：深刻理解和掌握0-1背包(动态规划算法、回溯算法)和背包(贪心算法)的问题描述、算法设计思想、程序设计、算法复杂性分析、他们的区别及联系。二. 设计内容1问题的描述(1) 0-1背包问题给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？(2)背包问题与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1=i=