beibao7.cpp

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

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

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

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

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

/*
	文件名称：beibao7
	项目名称：beibao7
	创建者：徐潇然
	创建时间：9/26/2006
	最后修改时间：9/26/2006
	功能：用动态规划算法解决0/1背包问题 
	文件中的函数名称和简单功能描述：
		Cbeibao7::input()：输入关于背包问题的数据信息（背包总重量total_weight，物品件数number，
				 及每个物品的重量和价值），并为成员指针weight，value，f开辟动态空间
		Cbeibao7::output()：解问题，输出最大总价值和最优方案
		Cbeibao7::solution()：用动态规划算法解问题
	文件中用到的他处定义的全局变量及其出处：无
	与其他文件的依赖关系：无
*/

#include <iostream>
using namespace std;

typedef double * ptrdouble;

/*
	类名称：Cbeibao7
	定义该类的目的：用动态规划算法解决0/1背包问题，并给出最优方案
	类属性：
	类中函数及功能：
		input()：输入关于背包问题的数据信息（背包总重量total_weight，物品件数number，
				 及每个物品的重量和价值），并为成员指针weight，value，f开辟动态空间
		output()：解问题，输出最大总价值和最优方案
		solution()：用动态规划算法解问题
	与其他类的关系（调用/被调用哪类对象中的什么函数）：无
*/
class Cbeibao7{
private:
	int total_weight; //背包能容纳的总重量
	int number; //物品件数
	int *weight; //指向一个记录每个物品重量的数组
	double *value; //指向一个记录每个物品价值的数组

	double **f; //动态规划中指向二维数组表的二级指针

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

/*
	函数名称：solution
	函数功能描述：用动态规划算法解问题
*/
	void solution();

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

/*
	函数名称：~Cbeibao7
	函数功能描述：析构函数，并释放先前开辟的动态变量空间
*/
	~Cbeibao7(){
		delete weight;
		delete value;
		for(int i=0;i<number;i++)
			delete f[i];
	}
};

void Cbeibao7::input(){
	cout<<"请输入背包可容纳的总重量(整数)w=";
	cin>>total_weight;
	cout<<"请输入物品的件数n=";
	cin>>number;
	cout<<"请分别输入这"<<number<<"个物品的重量(整数):\n";
	int i;
	weight=new int[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];
	
	f=new ptrdouble[number]; //建立一个number*total_weight的数组，来储存每个阶段的最大总价值
							 //f[i][t]表示在背包容量为t，有物品n，n-1，……，i（物品序号）的
							 //情况下的最大总价值
	for(i=0;i<number;i++)
		f[i]=new double[total_weight+1];
}

void Cbeibao7::output(){
	solution();

	cout<<"最大总价值为"<<f[0][total_weight]<<endl;
	cout<<"方案为(所取物品序号):\n";
	int i,T=total_weight;
	for(i=0;i<number-1;i++){
		if(f[i][T]!=f[i+1][T]){ //若当前阶段的最大价值f[i][T]等于前一阶段的值f[i+1][T]
			                    //说明第i个物品没有被选取；若不等，说明选取
			cout<<i+1<<"  ";
			T-=weight[i];
		}
	}
	cout<<endl;
}

void Cbeibao7::solution(){
	int i=number-1,t;
	
	//这两个for循环提供动态规划的初始值f[number-1][t],(t=0,1,2,3,……,total_weight)
	for(t=0;t<weight[i];t++)
		f[i][t]=0;
	for(;t<=total_weight;t++)
		f[i][t]=value[i];

	for(i=i-1;i>=0;i--){
		for(t=0;t<weight[i];t++) //当背包容量t小于第i个物品的重量时，显然物品i不可能被选
			f[i][t]+=f[i+1][t];
		for(;t<=total_weight;t++){//当t>=weight[i],两类情况：选或不选，取其大者
			if(f[i+1][t]>f[i+1][t-weight[i]]+value[i])
				f[i][t]=f[i+1][t];
			else
				f[i][t]=f[i+1][t-weight[i]]+value[i];
		}
	}
}

void main(){
	Cbeibao7 obj;
}