knapsackhandler.h

vc实现的0-1背包问题

//////////////////////////////////////////////////////////////////////////
//
//									KnapsackHandler.h
//
//////////////////////////////////////////////////////////////////////////

#ifndef KNAPSACKHANDLER_H_H
#define KNAPSACKHANDLER_H_H

#include "Item.h"
#include "Knapsack.h"
#include <IOSTREAM>
#include <FSTREAM>
using namespace std;


template <class TProfit, class TWeight>
class KnapsackHandler
{
public:
	KnapsackHandler(int count = DefItemsCount) {						//constructor
		m_ItemsCount = count;
		m_pKnapsack = new Knapsack<TProfit, TWeight>;
		m_Items = new Item<TProfit, TWeight>[m_ItemsCount];
	}

	~KnapsackHandler() {												//destruction
		if (m_pKnapsack != NULL)
			delete m_pKnapsack;
		if (m_Items != NULL) {
			delete []m_Items;
		}
	}

	void Initialize();													

	void SetItemsAttributes(ifstream& in);								//从ItemsData.txt中读取物品的价值和重量信息

	void OptimalSolution(ofstream& out);								//求最优解，结果保存到Solution.txt
	
	friend TProfit Max(TProfit a, TProfit b){						
		return a > b ? a : b;
	}
private:
	Knapsack<TProfit, TWeight>* m_pKnapsack;
	Item<TProfit, TWeight>* m_Items;
	int m_ItemsCount;
};

#endif //KNAPSACKHANDLER_H_H


template <class TProfit, class TWeight>
void KnapsackHandler<TProfit, TWeight>::Initialize(){
	ifstream in("ItemsData.txt");
	ofstream out("Solution.txt");

	SetItemsAttributes(in);

	OptimalSolution(out);
}

template <class TProfit, class TWeight>
void KnapsackHandler<TProfit, TWeight>::SetItemsAttributes(ifstream& in) {
	int Pi, Wi;
	
	Item<TProfit, TWeight> aItem;	
	for (int i = 0; i < m_ItemsCount; i++) {
		in>>Pi>>Wi;				//依次读取物品的价值和重量，并放入m_Items中保存
		aItem.SetProfit(Pi);
		aItem.SetWeight(Wi);
		m_Items[i] = aItem;
	}
}

template <class TProfit, class TWeight>
void KnapsackHandler<TProfit, TWeight>::OptimalSolution(ofstream& out) {
//////////////////////////////////////////////////////////////////////////
//def: V[i][j]是能够放进承重为j的背包中的前i个物品中最有价值子集的总价值，
//	   则V[n][W]，即n个给定物品中能够放进承重为W的背包的子集的最大总价值。
//
//				max{V[i-1][j], Pi + V[i-1][j-Wi]},	j - Wi ≥ 0
//V[i][j] = ｛															（1）
//							V[i-1][j]			 ,	j - Wi ＜ 0
//
//当 j ≥ 0 时，V[0][j] = 0; 当 i ≥ 0 时，V[i][0] = 0;					（2）
//////////////////////////////////////////////////////////////////////////

	TProfit V[DefItemsCount + 1][DefKnapsackCapacity + 1];

	int k,i,j;
	for (k = 0; k <= DefItemsCount; k++)								//（2）
		V[k][0] = 0;
	for (k = 0; k <= DefKnapsackCapacity; k++)
		V[0][k] = 0;

	int Wi = 0, Pi = 0;
	for (i = 1; i <= DefItemsCount; i++) {
		for (j = 1; j <= DefKnapsackCapacity; j++) {					//（1）
			Wi = m_Items[i - 1].GetWeight();
			Pi = m_Items[i - 1].GetProfit();
			if (j < Wi)													//j - Wi ＜ 0
				V[i][j] = V[i - 1][j];
			else {
				V[i][j] = Max(V[i - 1][j], Pi + V[i - 1][j - Wi]);		//j - Wi ≥ 0
			}
		}
	}
	
	//回溯V[i][j]表，求得最优子集的组成元素
	int Count = 0;
	j = DefKnapsackCapacity;
	for (i = DefItemsCount; i > 0; i--){
		if (V[i][j] != V[i - 1][j] && j >= 0) {						//V[i][j] != V[i - 1][j]，则第i个物品是最优子集的一部分
			m_pKnapsack->AddItem(m_Items[i - 1]);					//将第i个物品m_Item[i - 1]放进背包中
			j -= m_Items[i - 1].GetWeight();						//下次循环判断V[i-1][j-Wi]
			Count++;												//计数
		}
	}
	
// 	out<<"Knapsack Capacity: "<<DefKnapsackCapacity<<"; Items Count: "<<DefItemsCount<<'	'<<endl;
//	for (int a = 0; a <= DefItemsCount; a++) {
//		for (int b = 0; b <= DefKnapsackCapacity; b++)	
//			out<<V[a][b]<<'	';
//
//		out<<endl;
// 	}
	out<<"最优解的物品总价值为： "<<V[DefItemsCount][DefKnapsackCapacity]<<endl;
	out<<"取得最优解时背包容量： "<<DefKnapsackCapacity - m_pKnapsack->GetRemainCapacity()<<endl;
	out<<"最优解背包中物品数目： "<<m_pKnapsack->GetItemsCount()<<endl;
	out<<"物品(价值,重量)分别为："<<endl;

	Item<int, int>* items = new Item<int, int>[Count];
	m_pKnapsack->GetItems(items);								//取得包中存放的物品，通过数组items中返回
	for (i = 0; i < Count; i++)									
		out<<"("<<items[i].GetProfit()<<","<<items[i].GetWeight()<<")"<<' ';
	
	delete []items;
}