knapsack.h

vc实现的0-1背包问题

//////////////////////////////////////////////////////////////////////////
//
//									Knapsack.h
//
//////////////////////////////////////////////////////////////////////////

#ifndef KNAPSACK_H_H
#define KNAPSACK_H_H

#include "Item.h"
//#include <IOSTREAM>
#include <FSTREAM>

using namespace std;

template <class TProfit, class TWeight>
class Knapsack {
public:
	Knapsack(TWeight t = DefKnapsackCapacity) {						//construction
		m_TotalCapacity = t;
		m_RemainCapacity = m_TotalCapacity;
		m_CurItemsCount = -1;
		m_CurProfit = 0;
		m_MaxItemsCount = DefItemsCount;
		m_Items = new Item<TProfit, TWeight>[m_MaxItemsCount];
	}

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

	TProfit GetItemsProfit() const {								//取得当前背包中物品的价值
		return m_CurProfit;
	}

	TWeight GetRemainCapacity() const {								//取得当前背包的剩余容量
		return m_RemainCapacity;
	}

	void GetItems(Item<TProfit, TWeight> items[]) const {			//取得当前背包存放的物品，存入item[]数组中
		for (int i = 0; i <= m_CurItemsCount; i++)
			items[i] = m_Items[i];
	}

	int GetItemsCount() const {										//取得当前背包存放的物品数目
		return m_CurItemsCount + 1;
	}

	bool AddItem(const Item<TProfit, TWeight>& item);				//放入物品

	bool RemoveItem(const Item<TProfit, TWeight>& item);			//取出物品

	bool IsFull() const {											//背包是否已满
		return m_RemainCapacity <= 0 ? true : false;
	}

private:
	TWeight m_TotalCapacity;										//最大容量
	TWeight m_RemainCapacity;										//剩余容量
	TProfit m_CurProfit;											//当前背包中物品的价值
	Item<TProfit, TWeight>* m_Items;								//存放的物品
	int m_MaxItemsCount;											//最多可以存放的物品数
	int m_CurItemsCount;											//当前存放的物品数目
	void AppendItemsCount(int newCount);							//扩充m_Items数组容量

};

#endif //KNAPSACK_H_H

template <class TProfit, class TWeight>
bool Knapsack<TProfit, TWeight>::AddItem(const Item<TProfit, TWeight>& item) {
	bool ret = false;
	if (item.GetWeight() <= m_RemainCapacity) {			//如果物品重量小于背包承重量，物品存放入包
		m_RemainCapacity -= item.GetWeight();
		m_CurItemsCount++;
		if(GetItemsCount() >= m_MaxItemsCount)			//物品数目超出背包可以存放的最大物品数目，扩充m_Items空间
			AppendItemsCount(m_MaxItemsCount + ItemsCountInc);
		
		m_CurProfit += item.GetProfit();
		m_Items[m_CurItemsCount] = item;
		ret = true;
	}
	return ret;
}

template <class TProfit, class TWeight>
bool Knapsack<TProfit, TWeight>::RemoveItem(const Item<TProfit, TWeight>& item) {
	bool ret = false;
	if (m_CurItemsCount > 0) {							//如果包中有物品，取出
		m_RemainCapacity += item.GetWeight();
		m_CurProfit -= item.GetProfit();
		ret = true;
	}
	return ret;
}

template <class TProfit, class TWeight>
void Knapsack<TProfit, TWeight>::AppendItemsCount(int newCount) {
	if (newCount < m_MaxItemsCount) {
		exit(1);
	}
	if (newCount > m_MaxItemsCount) {
		Item<TProfit, TWeight>* newItems = new Item<TProfit, TWeight>[newCount];
		for (int i = 0; i < m_MaxItemsCount; i++)
			newItems[i] = m_Items[i];
		
		delete []m_Items;
		m_MaxItemsCount = newCount;
		m_Items = newItems;
	}
}