分别用回溯法和分支限界法求解0-1背包问题(共8页).doc

精选优质文档-倾情为你奉上华北水利水电学院 数据结构与算法分析 实验报告2009 2010 学年 第 1 学期 2009 级 计算机 专业班级： 学号： 姓名： 郜莉洁 一、 实验题目：分别用回溯法和分支限界法求解0-1背包问题二、 实验内容：0-1背包问题： 给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。三、 程序源代码：A:回溯法：/ bag1.cpp : Defines the entry point for the console application./#include stdafx.h#include #define MaxSize 100 /最多物品数