文件名称：实验五：01背包问题的回溯算法设计
文件大小：63KB
文件格式：DOC
更新时间：2015-05-14 15:32:15
算法设计与实现 01背包 回溯法
实验目的：0/1背包问题的回溯算法设计 实验原理：回溯算法设计。 实验要求：基本掌握回溯算法设计的原理方法。熟练掌握VC++中编程实现算法的常用技术和方法。 算法思想: 0-1背包问题:给定n种物品和一背包.物品i的重量是wi, 其价值为ui,背包的容量为C. 问如何选择装入背包的物品,使得装入背包中物品的总价值最大? 分析: 0-1背包是子集合选取问题,一般情况下0-1背包是个NP问题. 第一步 确定解空间：装入哪几种物品 第二步 确定易于搜索的解空间结构： 可以用数组p,w分别表示各个物品价值和重量。 用数组x记录，是否选种物品 第三步 以深度优先的方式搜索解空间，并在搜索的过程中剪枝