0-1背包问题

实验四“0-1”背包问题

一、 实验目的与要求

熟悉C/C++语言的集成开发环境；

通过本实验加深对贪心算法、动态规划算法的理解。

二、 实验内容:

掌握贪心算法、动态规划算法的概念和基本思想，分析并掌握“0-1”背包问题的求解

方法，并分析其优缺点。

三、 实验题

1. “0-1”背包问题的贪心算法

2. “0-1”背包问题的动态规划算法

说明：背包实例采用教材P132习题六的6-1中的描述。要求每种的算法都给出最大收

益和最优解。

设有背包问题实例n=7，M=15,，(w0,w1,。。。w6)=（2,3,5,7,1,4,1），物品装入背

包的收益为：（p0，p1，。。。，p6）=（10,5,15,7,6,18,3）。求这一实例的最优解和最大

收益。

四、 实验步骤

理解算法思想和问题要求；

编程实现题目要求；

上机输入和调试自己所编的程序；

验证分析实验结果；

整理出实验报告。

五、 实验程序

第1页下一页