// 我真誠(chéng)地保證：
    
// 我自己獨(dú)立地完成了整個(gè)程序從分析、設(shè)計(jì)到編碼的所有工作。
// 如果在上述過(guò)程中，我遇到了什么困難而求教于人，那么，我將在程序?qū)嵙?xí)報(bào)告中
// 詳細(xì)地列舉我所遇到的問(wèn)題，以及別人給我的提示。

// 在此，我感謝 XXX, …, XXX對(duì)我的啟發(fā)和幫助。下面的報(bào)告中，我還會(huì)具體地提到
// 他們?cè)诟鱾€(gè)方法對(duì)我的幫助。
 
// 我的程序里中凡是引用到其他程序或文檔之處，
// 例如教材、課堂筆記、網(wǎng)上的源代碼以及其他參考書(shū)上的代碼段,
// 我都已經(jīng)在程序的注釋里很清楚地注明了引用的出處。

// 我從未沒(méi)抄襲過(guò)別人的程序，也沒(méi)有盜用別人的程序，
// 不管是修改式的抄襲還是原封不動(dòng)的抄襲。

// 我編寫(xiě)這個(gè)程序，從來(lái)沒(méi)有想過(guò)要去破壞或妨礙其他計(jì)算機(jī)系統(tǒng)的正常運(yùn)轉(zhuǎn)。
    
// 徐瀟然 00548065 智能科學(xué)系

/*
	文件名稱：beibao3
	項(xiàng)目名稱：beibao3
	創(chuàng)建者：徐瀟然
	創(chuàng)建時(shí)間：9/26/2006
	最后修改時(shí)間：9/26/2006
	功能：用遞歸枚舉算法解決0/1背包問(wèn)題
	文件中的函數(shù)名稱和簡(jiǎn)單功能描述：
		Cbeibao3::input()：輸入關(guān)于背包問(wèn)題的數(shù)據(jù)信息（背包總重量total_weight，物品件數(shù)number，
				 及每個(gè)物品的重量和價(jià)值），并為成員指針weight，value開(kāi)辟動(dòng)態(tài)空間
		Cbeibao3::output()：解問(wèn)題，輸出最大總價(jià)值
		Cbeibao3::f(double,int)：用遞歸枚舉算法對(duì)0/1背包問(wèn)題進(jìn)行求解
	文件中用到的他處定義的全局變量及其出處：無(wú)
	與其他文件的依賴關(guān)系：無(wú)
*/
#include <iostream>
using namespace std;

/*
	類名稱：Cbeibao3
	定義該類的目的：用遞歸枚舉算法解決0/1背包問(wèn)題
	類屬性：
	類中函數(shù)及功能：
		input()：輸入關(guān)于背包問(wèn)題的數(shù)據(jù)信息（背包總重量total_weight，物品件數(shù)number，
				 及每個(gè)物品的重量和價(jià)值），并為成員指針weight，value開(kāi)辟動(dòng)態(tài)空間
		output()：解問(wèn)題，輸出最大總價(jià)值
		f(double,int)：用遞歸枚舉算法對(duì)0/1背包問(wèn)題進(jìn)行求解
	與其他類的關(guān)系（調(diào)用/被調(diào)用哪類對(duì)象中的什么函數(shù)）：無(wú)
*/
class Cbeibao3{
private:
	double total_weight; //背包能容納的總重量
	int number; //物品件數(shù)
	double *weight;//指向一個(gè)記錄每個(gè)物品重量的數(shù)組
	double *value; //指向一個(gè)記錄每個(gè)物品價(jià)值的數(shù)組

/*
	函數(shù)名稱：input
	函數(shù)功能描述：輸入關(guān)于背包問(wèn)題的數(shù)據(jù)信息（背包總重量total_weight，物品件數(shù)number，
				  及每個(gè)物品的重量和價(jià)值），并為成員指針weight，value開(kāi)辟動(dòng)態(tài)空間
*/
	void input();

/*
	函數(shù)名稱：f
	函數(shù)功能描述：用遞歸枚舉算法對(duì)0/1背包問(wèn)題進(jìn)行求解
	返回值：當(dāng)前最大總價(jià)值
	函數(shù)的輸入?yún)?shù)：T表示背包剩余容量，n表示物品序號(hào)（函數(shù)從n開(kāi)始枚舉至1）
*/
	double f(double T,int n);

/*
	函數(shù)名稱：output
	函數(shù)功能描述：解問(wèn)題，輸出最大總價(jià)值
*/
	void output();
public:
/*
	函數(shù)名稱：Cbeibao3
	函數(shù)功能描述：構(gòu)造函數(shù)，并實(shí)現(xiàn)問(wèn)題的讀入和答案的輸出，從而解決該問(wèn)題
*/
	Cbeibao3(){
		input();
		output();
	}

/*
	函數(shù)名稱：~Cbeibao3
	函數(shù)功能描述：析構(gòu)函數(shù)，并釋放先前開(kāi)辟的動(dòng)態(tài)變量空間
*/
	~Cbeibao3(){
		delete weight;
		delete value;
	}
};

void Cbeibao3::input(){
	cout<<"請(qǐng)輸入背包可容納的總重量w=";
	cin>>total_weight;
	cout<<"請(qǐng)輸入物品的件數(shù)n=";
	cin>>number;
	cout<<"請(qǐng)分別輸入這"<<number<<"個(gè)物品的重量:\n";
	int i;
	weight=new double[number];
	for(i=0;i<number;i++)
		cin>>weight[i];
	cout<<"請(qǐng)分別輸入這"<<number<<"個(gè)物品的價(jià)值:\n";
	value=new double[number];
	for(i=0;i<number;i++)
		cin>>value[i];
}

void Cbeibao3::output(){
	cout<<"最大價(jià)值為"<<f(total_weight,number)<<endl;
}

double Cbeibao3::f(double T,int n){
	int a,b;
	if(T==0||n==0)
		return 0;
	a=f(T,n-1); 
	if(T<weight[n-1]) //物品不能選
		return a;
	if(T>=weight[n-1]){ //物品可以選也可不選
		b=f(T-weight[n-1],n-1)+value[n-1];
		return a>b?a:b; //返回最大值
	}
}

void main(){
	Cbeibao3 obj;
}