《算法分析与设计》

实验报告

2015-2016年第2学期

实验班级： 学生姓名： 学 号： 指导老师：

信息工程学院

实验项目名称：回溯算法解决0-1背包问题 实验日期：2016年 5 月18 日

√验证性 □设计性 一、实验类型： □

二、实验目的

掌握0—1背包问题的回溯算法

三、实验内容及要求

给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

四、实验步骤

#include using namespace std; class Knap

{ friend int Knapsack(int p[],int w[],int c,int n ); public:

void print() { }; private:

int Bound(int i); void Backtrack(int i); int c;//背包容量 int n; //物品数 int *w;//物品重量数组 int *p;//物品价值数组

for(int m=1;m<=n;m++) { }

cout<

cout<

int cw;//当前重量 int cp;//当前价值 int bestp;//当前最优值 int *bestx;//当前最优解 int *x;//当前解 };

int Knap::Bound(int i) {

}

//计算上界

int cleft=c-cw;//剩余容量 int b=cp;

//以物品单位重量价值递减序装入物品 while(i<=n&&w[i]<=cleft) { }

//装满背包 if(i<=n)

b+=p[i]/w[i]*cleft; cleft-=w[i]; b+=p[i]; i++;

return b;

void Knap::Backtrack(int i) {

if(i>n) {

if(bestp

for(int j=1;j<=n;j++) bestx[j]=x[j];