beibao1_0.cpp

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

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

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

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

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

/*
	文件名称：beibao1_0
	项目名称：beibao1_0
	创建者：徐潇然
	创建时间：9/26/2006
	最后修改时间：9/26/2006
	功能：用递归枚举解决与利润无关背包问题
	文件中的函数名称和简单功能描述：
		Cbeibao1_0::input()：输入关于背包问题的数据信息（背包总重量total_weight，物品件数number，
				 及每个物品的重量），并为成员指针weight开辟动态空间
		Cbeibao1_0::output()：判断有无解，若有解给出一组解
		Cbeibao1_0::f(double,int)：用递归枚举算法对与利润无关背包问题求解
	文件中用到的他处定义的全局变量及其出处：无
	与其他文件的依赖关系：无
*/
#include <iostream>
using namespace std;

/*
	类名称：Cbeibao1_0
	定义该类的目的：用递归枚举解决与利润无关背包问题
	类属性：
	类中函数及功能：
		input()：输入关于背包问题的数据信息（背包总重量total_weight，物品件数number，
				 及每个物品的重量），并为成员指针weight开辟动态空间
		output()：判断有无解，若有解给出一组解
		f(double,int)：用递归枚举算法对与利润无关背包问题求解
	与其他类的关系（调用/被调用哪类对象中的什么函数）：无
*/
class Cbeibao1_0{
private:
	double total_weight; //背包能容纳的总重量
	int number; //物品件数
	double *weight;//指向一个记录每个物品重量的数组

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

/*
	函数名称：output
	函数功能描述：判断有无解，若有解给出一组解
*/
	void output();

/*
	函数名称：f
	函数功能描述：用递归枚举算法对与利润无关背包问题求解
	返回值：bool型，有解为true；无解为false
	函数的输入参数：背包剩余容量，物品序号（从n开始）
*/
	bool f(double,int);
public:
	Cbeibao1_0(){
		input();
		output();
	}
	~Cbeibao1_0(){
		delete weight;
	}
};

void Cbeibao1_0::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];
}

void Cbeibao1_0::output(){
	if(f(total_weight,number)==true)
		cout<<"为问题的一组重量解,问题有解\n";
	else
		cout<<"问题无解\n";
}

bool Cbeibao1_0::f(double T,int n){
	if(T==0) return true; //恰好装满，为真
	if(T<0 || (T>0&&n<1)) //溢出或不足，为假
		return false;
	if(f(T-weight[n-1],n-1)==true){
		cout<<weight[n-1]<<' '; //选取当前物品，且结果为真，输出（重量）
		return true;
	}
	else 
		return f(T,n-1); //否则，不选
}

void main(){
	Cbeibao1_0 obj;
}