knapsack.h

用动态规划来解背包问题,很不错的算法

#ifndef KNAPSACK_H 
#define KNAPSACK_H

using namespace std;

const int MAX_COUNT_OF_WIDGETS = 16; 
const int MAX_CAPACITY_OF_KNAPSACK = 15; 

/* This struct widget is defined. */ 
struct Widget 
{ 
	int		m_iID; 
	int		m_iVolume; 
	int		m_iValue; 
	bool	m_bSelected; 
}; 

/* This struct knapsack is defined */ 
struct Knapsack 
{ 
	int		m_iCapacity;
	int		m_iValue;
}; 

/* 
* This struct will be used in DynamicPrograming(). 
* m_iMaxValue indicates the maximum value can be achieved when the count of 
* widgets is i and the capacity of the knapsack is j; 
* m_bSelected indicates to achieve the maximum value whether the i-th widget 
* is selected under the same condition stated above. 
*/ 
struct MemeorizeMark 
{ 
	int		m_iMaxValue; 
	bool	m_bSelected; 
}; 

class SolveKnapsack 
{ 
public: 
	bool Init(); 
	bool DynamicProgramming(); 
	void PrintMaxValue()const; 
	void PrintSelection()const; 

private: 
	Knapsack		m_Knapsack; 
	Widget			m_Widget[MAX_COUNT_OF_WIDGETS]; 
	int				m_iCountOfWidgets; 
	MemeorizeMark	m_MemeorizeMark[MAX_COUNT_OF_WIDGETS][MAX_CAPACITY_OF_KNAPSACK]; 
}; 

#endif