// 我真誠地保證：
    
// 我自己獨立地完成了整個程序從分析、設計到編碼的所有工作。
// 如果在上述過程中，我遇到了什么困難而求教于人，那么，我將在程序實習報告中
// 詳細地列舉我所遇到的問題，以及別人給我的提示。

// 在此，我感謝 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{
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(){
		input();
		output();
	}
	~Cbeibao1(){
		delete weight;
	}
};

void Cbeibao1::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::output(){
	if(f(total_weight,number)==true)
		cout<<"問題有解\n";
	else
		cout<<"問題無解\n";
}

bool Cbeibao1::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)
		return true;//選取當前物品，且結果為真，返回真
	else 
		return f(T,n-1);//否則，不選
}

void main(){
	Cbeibao1 obj;
}