实验四“01”背包问题
一、实验目的与要求
熟悉CC语言的集成开发环境;
通过本实验加深对贪心算法、动态规划算法的理解。
二、
实验内容实验内容
掌握贪心算法、动态规划算法的概念和基本思想,分析并掌握“01”背包问题的求解
方法,并分析其优缺点。
三、
12
实验题
“01”背包问题的贪心算法
“01”背包问题的动态规划算法
说明:背包实例采用教材P132习题六的61中的描述。要求每种的算法都给出最大收
益和最优解。
设有背包问题实例
7,M15,w0w1。。w6(2357141)。,物品装入背
包的收益为:(p0,p1,。,p6)(1051576183)。。。求这一实例的最优解和最大
收益。
四、
实验步骤
理解算法思想和问题要求;
编程实现题目要求;
上机输入和调试自己所编的程序;
验证分析实验结果;
整理出实验报告。
五、
实验程序
f贪心法求解i
cludeiostreami
clude