第 页 共 页 华北水利水电学院 数据结构与算法分析 实验报告 2009 ～2010 学年 第 1 学期 2009 级 计算机 专业 班级： 2 0 0 9 1 5 3 2 6 学号： 2 0 0 9 1 5 3 2 6 姓名： 郜莉洁 一、 实验题目： 分别用回溯法和分支限界法求解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 //最多物品数 int limitw; //限制的总重量 int maxwv=0; //存放最优解的总价值 int maxw; int n; //实际物品数 int option[MaxSize]; // 存放最终解 int op[MaxSize]; //存放临时解 struct { int weight; int value; }a[MaxSize]; //存放物品数组 void Knap( int i, int tw, int tv) //考虑第i 个物品 { int j; if(i>=n) //找到一个叶子结点 { if (tw<=limitw && tv>maxwv) //找到一个满足条件地更优解，保存它 { maxwv=tv; maxw=tw; for(j=0;j #include
VIP
