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

// 在此，我感謝 XXX, …, XXX對我的啟發和幫助。下面的報告中，我還會具體地提到
// 他們在各個方法對我的幫助。
 
// 我的程序里中凡是引用到其他程序或文檔之處，
// 例如教材、課堂筆記、網上的源代碼以及其他參考書上的代碼段,
// 我都已經在程序的注釋里很清楚地注明了引用的出處。

// 我從未沒抄襲過別人的程序，也沒有盜用別人的程序，
// 不管是修改式的抄襲還是原封不動的抄襲。

// 我編寫這個程序，從來沒有想過要去破壞或妨礙其他計算機系統的正常運轉。
    
// 徐瀟然 00548065 智能科學系

/*
	文件名稱：beibao4
	項目名稱：beibao4
	創建者：徐瀟然
	創建時間：9/26/2006
	最后修改時間：9/26/2006
	功能：用回溯搜索算法解決0/1背包問題
	文件中的函數名稱和簡單功能描述：
		Cbeibao4::input()：輸入關于背包問題的數據信息（背包總重量total_weight，物品件數number，
				 及每個物品的重量和價值），并為成員指針weight，value開辟動態空間
		Cbeibao4::output()：解問題，輸出最大總價值和最優方案
		Cbeibao4::f(int i)：用回溯搜索算法對0/1背包問題進行求
	文件中用到的他處定義的全局變量及其出處：無
	與其他文件的依賴關系：無
*/
#include <iostream>
using namespace std;

/*
	類名稱：Cbeibao4
	定義該類的目的：用回溯搜索算法解決0/1背包問題，并給出最優方案
	類屬性：
	類中函數及功能：
		input()：輸入關于背包問題的數據信息（背包總重量total_weight，物品件數number，
				 及每個物品的重量和價值），并為成員指針weight，value等開辟動態空間
		output()：解問題，輸出最大總價值和最優方案
		f(int i)：用回溯搜索算法對0/1背包問題進行求解
	與其他類的關系（調用/被調用哪類對象中的什么函數）：無
*/
class Cbeibao4{
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; //當前取過物品的總重量

/*
	函數名稱：input
	函數功能描述：輸入關于背包問題的數據信息（背包總重量total_weight，物品件數number，
				  及每個物品的重量和價值），并為成員指針weight，value等開辟動態空間
*/
	void input();

/*
	函數名稱：f
	函數功能描述：用回溯搜索算法對0/1背包問題進行求解
	函數的輸入參數：i表示當前搜索深度
*/
	void f(int i); //i表示當前搜索深度

/*
	函數名稱：output
	函數功能描述：解問題，輸出最大總價值和最優方案
*/
	void output();
public:
/*
	函數名稱：Cbeibao4
	函數功能描述：構造函數，并實現問題的讀入和答案的輸出，從而解決該問題
*/
	Cbeibao4(){
		input();
		output();
	}

/*
	函數名稱：~Cbeibao4
	函數功能描述：析構函數，并釋放先前開辟的動態變量空間
*/
	~Cbeibao4(){
		delete weight;
		delete value;
		delete x_current;
		delete x_max;
	}
};

void Cbeibao4::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];
	for(i=0;i<number;i++)
		x_max[i]=0; //初始時最大總價值的物品組合為無
	max_value=0;//初始時最大總價值為0
	current_weight=0;//初始時當前重量和為0
}

void Cbeibao4::output(){
	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 Cbeibao4::f(int i){
	int j;
	if(i==number){ //到達葉結點
		sum_value=0;
		for(j=0;j<number;j++)
			sum_value=sum_value+value[j]*x_current[j];
		if(sum_value>max_value){
			max_value=sum_value;
			for(j=0;j<number;j++)//找到總價值更大的情況，更新取舍情況
				x_max[j]=x_current[j];
		}
		return;
	}

	x_current[i]=0;
	f(i+1);//不裝入物品i

	if(current_weight+weight[i]<=total_weight){//物品i滿足背包容量條件，可以選取
		current_weight+=weight[i];
		x_current[i]=1;
		f(i+1);
		current_weight-=weight[i];//回溯前清理現場
		x_current[i]=0;
	}
}

void main(){
	Cbeibao4 obj;
}