beibao5.cpp

八种背包问题的所有源代码

// 我真诚地保证：
    
// 我自己独立地完成了整个程序从分析、设计到编码的所有工作。
// 如果在上述过程中，我遇到了什么困难而求教于人，那么，我将在程序实习报告中
// 详细地列举我所遇到的问题，以及别人给我的提示。

// 在此，我感谢 XXX, …, XXX对我的启发和帮助。下面的报告中，我还会具体地提到
// 他们在各个方法对我的帮助。
 
// 我的程序里中凡是引用到其他程序或文档之处，
// 例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段,
// 我都已经在程序的注释里很清楚地注明了引用的出处。

// 我从未没抄袭过别人的程序，也没有盗用别人的程序，
// 不管是修改式的抄袭还是原封不动的抄袭。

// 我编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转。
    
// 徐潇然 00548065 智能科学系

/*
	文件名称：beibao5
	项目名称：beibao5
	创建者：徐潇然
	创建时间：9/26/2006
	最后修改时间：9/26/2006
	功能：用加限界策略的优化回溯算法解决0/1背包问题
	文件中的函数名称和简单功能描述：
		Cbeibao5::input()：输入关于背包问题的数据信息（背包总重量total_weight，物品件数number，
				 及每个物品的重量和价值），并为成员指针weight，value开辟动态空间
		Cbeibao5::output()：解问题，输出最大总价值和最优方案
		Cbeibao5::sort()：按价值重量比从大到小排序，weight[]，value[]的内容不变，而将排序后的
				结果（物品序号）储存在索引表list中
		Cbeibao5::f(int i)：用加限界策略的优化回溯算法对0/1背包问题进行求解
		Cbeibao5::bound(int i); 限界函数
	文件中用到的他处定义的全局变量及其出处：无
	与其他文件的依赖关系：无
*/
#include <iostream>
using namespace std;

/*
	类名称：Cbeibao5
	定义该类的目的：用加限界策略的优化回溯算法解决0/1背包问题，并给出最优方案
	类属性：
	类中函数及功能：
		input()：输入关于背包问题的数据信息（背包总重量total_weight，物品件数number，
				 及每个物品的重量和价值），并为成员指针weight，value等开辟动态空间
		output()：解问题，输出最大总价值和最优方案
		sort()：按价值重量比从大到小排序，weight[]，value[]的内容不变，而将排序后的
				结果（物品序号）储存在索引表list中
		f(int i)：用加限界策略的优化回溯算法对0/1背包问题进行求解
		bound(int i); 限界函数		
	与其他类的关系（调用/被调用哪类对象中的什么函数）：无
*/
class Cbeibao5{
private:
	double total_weight; //背包能容纳的总重量
	int number; //物品件数
	double *weight;//指向一个记录每个物品重量的数组
	double *value; //指向一个记录每个物品价值的数组

	int *x_current; //当前分支的物品取舍情况
	int *x_max; //最大总价值时的物品取舍情况
	double sum_value; //当前分支的总价值
	double max_value; //最大总价值
	double current_weight; //当前取过物品的总重量
	int *list; //排序后的索引表

/*
	函数名称：input
	函数功能描述：输入关于背包问题的数据信息（背包总重量total_weight，物品件数number，
				  及每个物品的重量和价值），并为成员指针weight，value等开辟动态空间
*/
	void input();

/*
	函数名称：sort
	函数调用之前的预备条件：读取背包问题的数据信息
	函数功能描述：按价值重量比从大到小排序，weight[]，value[]的内容不变，而将排序后的
				结果（物品序号）储存在索引表list中
*/
	void sort();

/*
	函数名称：f
	函数调用之前的预备条件：对物品按价值重量比排序
	函数功能描述：用加限界策略的优化回溯非递归算法对0/1背包问题进行求解
	函数的输入参数：i表示当前搜索深度
*/
	void f(int i); 

/*
	函数名称：bound
	函数功能描述：限界函数
	返回值（如果有的话）：当前状态下不取物品i时能达到的最大总价值的上界
	函数的输入参数：当前状态下的物品序号
*/
	double bound(int i); //限界函数

/*
	函数名称：output
	函数功能描述：解问题，输出最大总价值和最优方案
*/
	void output();
public:
/*
	函数名称：Cbeibao5
	函数功能描述：构造函数，并实现问题的读入和答案的输出，从而解决该问题
*/
	Cbeibao5(){
		input();
		output();
	}

/*
	函数名称：~Cbeibao6
	函数功能描述：析构函数，并释放先前开辟的动态变量空间
*/
	~Cbeibao5(){
		delete weight;
		delete value;
		delete x_current;
		delete x_max;
	}
};

void Cbeibao5::input(){
	cout<<"请输入背包可容纳的总重量w=";
	cin>>total_weight;
	cout<<"请输入物品的件数n=";
	cin>>number;
	cout<<"请分别输入这"<<number<<"个物品的重量:\n";
	int i;
	weight=new double[number];
	for(i=0;i<number;i++)
		cin>>weight[i];
	cout<<"请分别输入这"<<number<<"个物品的价值:\n";
	value=new double[number];
	for(i=0;i<number;i++)
		cin>>value[i];
	
	x_max=new int[number];
	x_current=new int[number];
	list=new int[number];
	for(i=0;i<number;i++)
		x_max[i]=0; //初始时最大总价值的物品组合为无
	max_value=0; //初始时最大总价值为0
	current_weight=0; //初始时当前重量和为0
	sum_value=0; //初始时当前总价值为0
}

void Cbeibao5::output(){
	sort();
	f(0);

	cout<<"最大总价值为"<<max_value<<endl;
	cout<<"方案为(所取物品序号):\n";
	int i;
	for(i=0;i<number;i++){
		if(x_max[i]==1) //若x_max[i]值为0，没选该物品；为1，则选
			cout<<i+1<<"  ";
	}
	cout<<endl;
}

void Cbeibao5::f(int i){
	int j;
	if(i==number){ //到达叶结点
		if(sum_value>max_value){
			max_value=sum_value;
			for(j=0;j<number;j++)//找到总价值更大的情况，更新取舍情况
				x_max[j]=x_current[j];
		}
		return;
	}

	if(current_weight+weight[list[i]]<=total_weight){//物品i满足背包容量条件，可以选取
		current_weight+=weight[list[i]];
		sum_value+=value[list[i]];
		x_current[list[i]]=1;
		f(i+1);
		current_weight-=weight[list[i]]; //回溯前清理现场
		sum_value-=value[list[i]];
		x_current[list[i]]=0;
	}	
	
	if(bound(i)>max_value){ //不装入物品i
		x_current[list[i]]=0;
		f(i+1);
	}
}

double Cbeibao5::bound(int i){
	double rest_weight=total_weight-current_weight; //背包剩余的容量
	double bound_value=sum_value;//返回的上界等于物品i前的总价值加上i后按连续背包问题算的价值和
	int j;
	for(j=i+1;j<number&&rest_weight>=weight[list[j]];j++){
		bound_value+=value[list[j]];
		rest_weight-=weight[list[j]];
	}
	if(j<number&&rest_weight>0)
		bound_value+=rest_weight*value[list[j]]/weight[list[j]]; //按照连续背包问题估计上界
	return bound_value;
}

void Cbeibao5::sort(){
	int i,j,max,*temp=new int[number];
	for(i=0;i<number;i++)
		temp[i]=0;
	for(i=0;i<number;i++){
		max=0;
		while(temp[max]==1)
			max++;
		for(j=1;j<number;j++){
			if(temp[j]==0 && value[j]/weight[j]>value[max]/weight[max])
				max=j;
		}
		temp[max]=1; //为已选出的物品作记号
		list[i]=max; //索引表，依价值重量比由大到小
	}
}

void main(){
	Cbeibao5 obj;
}