thethiefproblem.cpp.txt

0－1的小偷背包问题源码

/////////////////////////////////////////////////////////////
//
//卢新来.
//2006年1月
//
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
//简介：
//    这是一个小偷背包问题的算法.
//计算在小偷的背包所装重量允许范围内，最多可以偷到多少钱！
//
//数组vi保存各个东西的价值，数组wi保存对应的重量。
//二维数组maxV[i][j]保存在j重量下，从0到i件东西最多可以偷到的价值。
//二维数组RememberWhat[i][j]记录偷盗经历,即在j重量下，
//如果偷第i件东西能得到最大价值，那么数组保存1；否则保存0。
/////////////////////////////////////////////////////////////////

#include<iostream>
#include<string>
#include<set>

using namespace std ;

#define itemsNumbers 3
#define MaxWeightSteal 100
 
int TellMe(int RememberWhat[itemsNumbers + 1][MaxWeightSteal + 1] , int itemNumrs , int MaxWeight , int vi[itemsNumbers + 1] , int wi[itemsNumbers + 1])
{
	if(MaxWeight < 0 || itemNumrs < 1)
		return 0 ;

	if(1 == RememberWhat[itemNumrs][MaxWeight])
	{
		TellMe( RememberWhat, itemNumrs - 1, MaxWeight - wi[itemNumrs] , vi , wi) ;
		cout << "价值为 : " << vi[itemNumrs] << "\t" << " ,重量为" << "\t" << wi[itemNumrs] << endl ;
		return 0 ;
	}
	else
	{
		TellMe(RememberWhat, itemNumrs - 1 , MaxWeight , vi , wi) ;
		return 0 ;
	}
} 
 
void main()
{
	int i ;
	string h = "ok" ;

	while("ok" == h)
	{	
		cout << "您最多能偷重达" << MaxWeightSteal << "的东西！" << endl << endl ;
	
		int vi[itemsNumbers + 1] ;
		vi[0] = 0 ;
		cout << "请输入想偷的" << itemsNumbers << "个东西的各自价值(单位为元；注意输入整数)：" << endl ;
		for(i = 1 ; i <= itemsNumbers ; i ++)
			cin >> vi[i] ;

		int wi[itemsNumbers + 1] ;
		wi[0] = 0 ;
		cout << "请输入想偷的" << itemsNumbers << "个东西的各自重量(输入整数)：" << endl ;
		for(i = 1 ; i <= itemsNumbers ; i ++)
			cin >> wi[i] ;

		int maxV[itemsNumbers + 1][MaxWeightSteal + 1] ;
		for(i = 0 ; i <= MaxWeightSteal ; i ++) 
			maxV[0][i] = 0 ;
	
		int RememberWhat[itemsNumbers + 1][MaxWeightSteal + 1] ;
		for(i = 0 ; i <= itemsNumbers ; i ++) 
			maxV[i][0] = 0 ;

		/****************************开始偷！****************************/
		for(int remain_W = 1 ; remain_W <= MaxWeightSteal ; remain_W ++)
		{
			for(int i = 1 ; i <= itemsNumbers ; i ++)
			{
				if(remain_W < wi[i])
				{
					maxV[i][remain_W] = maxV[i-1][remain_W] ;
					RememberWhat[i][remain_W] = 0 ;
				}
				else
				{
					if(maxV[i-1][remain_W] > maxV[i-1][remain_W - wi[i]] + vi[i])
					{
						maxV[i][remain_W] = maxV[i-1][remain_W] ;
						RememberWhat[i][remain_W] = 0 ;
					}
					else
					{
						maxV[i][remain_W] = maxV[i-1][remain_W - wi[i]] + vi[i] ;
						RememberWhat[i][remain_W] = 1 ;
					}
				}             
			}
		}

		/*******************显示结果！*******************/
		if(maxV[itemsNumbers][MaxWeightSteal] != 0)
		{
			cout << "恭喜，这次你最多可以偷" << maxV[itemsNumbers][MaxWeightSteal] << "欧元的东西！" << endl ;
			cout << "分别是 ：" << endl ;
			
			/*********************打印偷到的东西！***********************/
			TellMe(RememberWhat , itemsNumbers , MaxWeightSteal , vi , wi) ;
		}
		else
			cout << "完蛋了，这次什么都偷不了！！！" << endl ;

		cout << "接着玩，输入ok；没劲，就输入别的退出吧!" << endl ;
			cin >> h ;
	}
}