knapsack.cpp

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

#include <iostream> 
#include "knapsack.h" 

using namespace std; 

bool SolveKnapsack::Init()
{ 
	/* initialize the knapsack */ 
	cout << "Pls input the capacity of knapsack(0 < capacity <= " << MAX_CAPACITY_OF_KNAPSACK << "): " << endl; 
	cin >> m_Knapsack.m_iCapacity;
	m_Knapsack.m_iCapacity += 1;

	if ((0 >= m_Knapsack.m_iCapacity) || ((MAX_CAPACITY_OF_KNAPSACK + 1) < m_Knapsack.m_iCapacity)) 
	{
		cout << "Capacity is not correct" << endl;
		return false;
	}
	else 
	{ 
		m_Knapsack.m_iValue = 0; 
	} 

	/* initialize the widgets */ 
	cout << "Pls input the count of widgets(0< count <= " << MAX_COUNT_OF_WIDGETS << "): " << endl; 
	cin >> m_iCountOfWidgets; 
	m_iCountOfWidgets += 1; 

	if ((0 >= m_iCountOfWidgets) || ((MAX_COUNT_OF_WIDGETS + 1) < m_iCountOfWidgets)) 
	{ 
		cout << "count of widgets is not correct" << endl; 
		return false; 
	} 
	else 
	{ 
		for (int i = 1; i < m_iCountOfWidgets; i++) 
		{ 
			m_Widget[i].m_iID = i; 

			cout << "Pls input widget[" << i << "]'s volume:" << endl; 
			cin >> m_Widget[i].m_iVolume; 
			if (m_Widget[i].m_iVolume <= 0) 
			{ 
				cout << "widget's volume is not correct" << endl; 
				return false; 
			} 

			cout << "Pls input widget[" << i << "]'s value:" << endl; 
			cin >> m_Widget[i].m_iValue; 
			if (m_Widget[i].m_iValue <= 0) 
			{ 
				cout << "widget's value is not correct" << endl; 
				return false; 
			} 

			m_Widget[i].m_bSelected = false; 
		}// end of for 
	}// end of if 

	/* initialize the MemeorizeMark */ 
	for (int i = 0; m_iCountOfWidgets > i; i++) 
	{ 
		for (int j = 0; m_Knapsack.m_iCapacity > j; j++) 
		{ 
			m_MemeorizeMark[i][j].m_iMaxValue = 0; 
			m_MemeorizeMark[i][j].m_bSelected = false; 
		} 
	} 

	return true; 
} 

bool SolveKnapsack::DynamicProgramming() 
{ 
	/* 
	* variable i stands for the current count of widgets; 
	* variable j stands for the current capacity of knapsack. 
	* 
	* The following code segment is to compute the value of the optimal 
	* solution using dynamic programming. 
	*/ 
	int i = 0; 
	int j = 0; 
	for (i = 1; m_iCountOfWidgets > i; i++) 
	{ 
		for (j = 1; m_Knapsack.m_iCapacity > j; j++) 
		{
			int i_iVolume = m_Widget[i].m_iVolume;
			if (i_iVolume <= j)
			{
				if ((m_MemeorizeMark[i-1][j-i_iVolume].m_iMaxValue + m_Widget[i].m_iValue) 
					>= 	m_MemeorizeMark[i-1][j].m_iMaxValue) 
				{ 
					m_MemeorizeMark[i][j].m_iMaxValue = m_MemeorizeMark[i-1][j-i_iVolume].m_iMaxValue + m_Widget[i].m_iValue; 
					m_MemeorizeMark[i][j].m_bSelected = true; 
				} 
				else 
				{ 
					m_MemeorizeMark[i][j].m_iMaxValue = m_MemeorizeMark[i-1][j].m_iMaxValue; 
					m_MemeorizeMark[i][j].m_bSelected = false; 
				} 
			} 
			else 
			{ 
				m_MemeorizeMark[i][j].m_iMaxValue = m_MemeorizeMark[i-1][j].m_iMaxValue; 
				m_MemeorizeMark[i][j].m_bSelected = false; 
			} 
		} 
	} 

	/* 
	* The following code segment is to contruct the optimal solution 
	* from the computed information. 
	*/ 
	i = m_iCountOfWidgets - 1; 
	j = m_Knapsack.m_iCapacity - 1; 

	m_Knapsack.m_iValue = m_MemeorizeMark[i][j].m_iMaxValue; 
	for ( ; 0 < i; i--) 
	{ 
		if (true == m_MemeorizeMark[i][j].m_bSelected) 
		{ 
			m_Widget[i].m_bSelected = true; 
			j = j - m_Widget[i].m_iVolume; 
		} 
	} 

	return true; 
} 

void SolveKnapsack::PrintMaxValue()const 
{ 
	cout << "Max value is: " << m_Knapsack.m_iValue << endl; 
} 

void SolveKnapsack::PrintSelection()const 
{ 
	for (int i = 1; i < m_iCountOfWidgets; i++) 
	{ 
		if (true == m_Widget[i].m_bSelected) 
		{ 
			cout << "Widget[" << i << "] is selected" << endl; 
		} 
	} 
} 


int main()
{
	SolveKnapsack SK; 
	if (true == SK.Init()) 
	{
		if (true == SK.DynamicProgramming()) 
		{ 
			SK.PrintMaxValue(); 
			SK.PrintSelection(); 
		}
	} 

	return 0; 
}