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

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

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

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

/*
	文件名稱：beibao5
	項目名稱：beibao5
	創(chuàng)建者：徐瀟然
	創(chuàng)建時間：9/26/2006
	最后修改時間：9/26/2006
	功能：用加限界策略的優(yōu)化回溯算法解決0/1背包問題
	文件中的函數(shù)名稱和簡單功能描述：
		Cbeibao5::input()：輸入關(guān)于背包問題的數(shù)據(jù)信息（背包總重量total_weight，物品件數(shù)number，
				 及每個物品的重量和價值），并為成員指針weight，value開辟動態(tài)空間
		Cbeibao5::output()：解問題，輸出最大總價值和最優(yōu)方案
		Cbeibao5::sort()：按價值重量比從大到小排序，weight[]，value[]的內(nèi)容不變，而將排序后的
				結(jié)果（物品序號）儲存在索引表list中
		Cbeibao5::f(int i)：用加限界策略的優(yōu)化回溯算法對0/1背包問題進行求解
		Cbeibao5::bound(int i); 限界函數(shù)
	文件中用到的他處定義的全局變量及其出處：無
	與其他文件的依賴關(guān)系：無
*/
#include <iostream>
using namespace std;

/*
	類名稱：Cbeibao5
	定義該類的目的：用加限界策略的優(yōu)化回溯算法解決0/1背包問題，并給出最優(yōu)方案
	類屬性：
	類中函數(shù)及功能：
		input()：輸入關(guān)于背包問題的數(shù)據(jù)信息（背包總重量total_weight，物品件數(shù)number，
				 及每個物品的重量和價值），并為成員指針weight，value等開辟動態(tài)空間
		output()：解問題，輸出最大總價值和最優(yōu)方案
		sort()：按價值重量比從大到小排序，weight[]，value[]的內(nèi)容不變，而將排序后的
				結(jié)果（物品序號）儲存在索引表list中
		f(int i)：用加限界策略的優(yōu)化回溯算法對0/1背包問題進行求解
		bound(int i); 限界函數(shù)		
	與其他類的關(guān)系（調(diào)用/被調(diào)用哪類對象中的什么函數(shù)）：無
*/
class Cbeibao5{
private:
	double total_weight; //背包能容納的總重量
	int number; //物品件數(shù)
	double *weight;//指向一個記錄每個物品重量的數(shù)組
	double *value; //指向一個記錄每個物品價值的數(shù)組

	int *x_current; //當前分支的物品取舍情況
	int *x_max; //最大總價值時的物品取舍情況
	double sum_value; //當前分支的總價值
	double max_value; //最大總價值
	double current_weight; //當前取過物品的總重量
	int *list; //排序后的索引表

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

/*
	函數(shù)名稱：sort
	函數(shù)調(diào)用之前的預(yù)備條件：讀取背包問題的數(shù)據(jù)信息
	函數(shù)功能描述：按價值重量比從大到小排序，weight[]，value[]的內(nèi)容不變，而將排序后的
				結(jié)果（物品序號）儲存在索引表list中
*/
	void sort();

/*
	函數(shù)名稱：f
	函數(shù)調(diào)用之前的預(yù)備條件：對物品按價值重量比排序
	函數(shù)功能描述：用加限界策略的優(yōu)化回溯非遞歸算法對0/1背包問題進行求解
	函數(shù)的輸入?yún)?shù)：i表示當前搜索深度
*/
	void f(int i); 

/*
	函數(shù)名稱：bound
	函數(shù)功能描述：限界函數(shù)
	返回值（如果有的話）：當前狀態(tài)下不取物品i時能達到的最大總價值的上界
	函數(shù)的輸入?yún)?shù)：當前狀態(tài)下的物品序號
*/
	double bound(int i); //限界函數(shù)

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

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

void Cbeibao5::input(){
	cout<<"請輸入背包可容納的總重量w=";
	cin>>total_weight;
	cout<<"請輸入物品的件數(shù)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];
	list=new int[number];
	for(i=0;i<number;i++)
		x_max[i]=0; //初始時最大總價值的物品組合為無
	max_value=0; //初始時最大總價值為0
	current_weight=0; //初始時當前重量和為0
	sum_value=0; //初始時當前總價值為0
}

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

	if(current_weight+weight[list[i]]<=total_weight){//物品i滿足背包容量條件，可以選取
		current_weight+=weight[list[i]];
		sum_value+=value[list[i]];
		x_current[list[i]]=1;
		f(i+1);
		current_weight-=weight[list[i]]; //回溯前清理現(xiàn)場
		sum_value-=value[list[i]];
		x_current[list[i]]=0;
	}	
	
	if(bound(i)>max_value){ //不裝入物品i
		x_current[list[i]]=0;
		f(i+1);
	}
}

double Cbeibao5::bound(int i){
	double rest_weight=total_weight-current_weight; //背包剩余的容量
	double bound_value=sum_value;//返回的上界等于物品i前的總價值加上i后按連續(xù)背包問題算的價值和
	int j;
	for(j=i+1;j<number&&rest_weight>=weight[list[j]];j++){
		bound_value+=value[list[j]];
		rest_weight-=weight[list[j]];
	}
	if(j<number&&rest_weight>0)
		bound_value+=rest_weight*value[list[j]]/weight[list[j]]; //按照連續(xù)背包問題估計上界
	return bound_value;
}

void Cbeibao5::sort(){
	int i,j,max,*temp=new int[number];
	for(i=0;i<number;i++)
		temp[i]=0;
	for(i=0;i<number;i++){
		max=0;
		while(temp[max]==1)
			max++;
		for(j=1;j<number;j++){
			if(temp[j]==0 && value[j]/weight[j]>value[max]/weight[max])
				max=j;
		}
		temp[max]=1; //為已選出的物品作記號
		list[i]=max; //索引表，依價值重量比由大到小
	}
}

void main(){
	Cbeibao5 obj;
}