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

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

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

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

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

#include <iostream>
using namespace std;

typedef double * ptrdouble;

/*
	類名稱：Cbeibao7
	定義該類的目的：用動態規劃算法解決0/1背包問題，并給出最優方案
	類屬性：
	類中函數及功能：
		input()：輸入關于背包問題的數據信息（背包總重量total_weight，物品件數number，
				 及每個物品的重量和價值），并為成員指針weight，value，f開辟動態空間
		output()：解問題，輸出最大總價值和最優方案
		solution()：用動態規劃算法解問題
	與其他類的關系（調用/被調用哪類對象中的什么函數）：無
*/
class Cbeibao7{
private:
	int total_weight; //背包能容納的總重量
	int number; //物品件數
	int *weight; //指向一個記錄每個物品重量的數組
	double *value; //指向一個記錄每個物品價值的數組

	double **f; //動態規劃中指向二維數組表的二級指針

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

/*
	函數名稱：solution
	函數功能描述：用動態規劃算法解問題
*/
	void solution();

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

/*
	函數名稱：~Cbeibao7
	函數功能描述：析構函數，并釋放先前開辟的動態變量空間
*/
	~Cbeibao7(){
		delete weight;
		delete value;
		for(int i=0;i<number;i++)
			delete f[i];
	}
};

void Cbeibao7::input(){
	cout<<"請輸入背包可容納的總重量(整數)w=";
	cin>>total_weight;
	cout<<"請輸入物品的件數n=";
	cin>>number;
	cout<<"請分別輸入這"<<number<<"個物品的重量(整數):\n";
	int i;
	weight=new int[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];
	
	f=new ptrdouble[number]; //建立一個number*total_weight的數組，來儲存每個階段的最大總價值
							 //f[i][t]表示在背包容量為t，有物品n，n-1，……，i（物品序號）的
							 //情況下的最大總價值
	for(i=0;i<number;i++)
		f[i]=new double[total_weight+1];
}

void Cbeibao7::output(){
	solution();

	cout<<"最大總價值為"<<f[0][total_weight]<<endl;
	cout<<"方案為(所取物品序號):\n";
	int i,T=total_weight;
	for(i=0;i<number-1;i++){
		if(f[i][T]!=f[i+1][T]){ //若當前階段的最大價值f[i][T]等于前一階段的值f[i+1][T]
			                    //說明第i個物品沒有被選取；若不等，說明選取
			cout<<i+1<<"  ";
			T-=weight[i];
		}
	}
	cout<<endl;
}

void Cbeibao7::solution(){
	int i=number-1,t;
	
	//這兩個for循環提供動態規劃的初始值f[number-1][t],(t=0,1,2,3,……,total_weight)
	for(t=0;t<weight[i];t++)
		f[i][t]=0;
	for(;t<=total_weight;t++)
		f[i][t]=value[i];

	for(i=i-1;i>=0;i--){
		for(t=0;t<weight[i];t++) //當背包容量t小于第i個物品的重量時，顯然物品i不可能被選
			f[i][t]+=f[i+1][t];
		for(;t<=total_weight;t++){//當t>=weight[i],兩類情況：選或不選，取其大者
			if(f[i+1][t]>f[i+1][t-weight[i]]+value[i])
				f[i][t]=f[i+1][t];
			else
				f[i][t]=f[i+1][t-weight[i]]+value[i];
		}
	}
}

void main(){
	Cbeibao7 obj;
}