bag_layout.cpp

这是经典的背包问题

#include<iostream.h>
////////////////////////////////////////////////////////////////////////////////
//用动态规划来实现
//假设n<=N=100和t<=T=100
#define N 101
#define T 101
bool pp[N][T];
bool bag_recursion_layout();//动态规划函数 有解返回1 否则 0
void bag_problem();//输入数组等辅助工作//判断背包是否有解

int n;//number of items
int*item;//pointer to the items' array
int t;//total capability

//////////////////////////////////////////////////////////////////////////



void bag_problem()
{
	cout<<"put in the number of the items and the total capability of the bag"<<endl;
	cin>>n>>t;
	item=new int[n+5];
	cout<<"put in the weight of each item"<<endl;
	for(int i=1;i<=n;i++)
		cin>>item[i];
	if(bag_recursion_layout())
		cout<<"yes"<<endl;
	else
		cout<<"no"<<endl;
	delete [] item;
}


bool bag_recursion_layout()
{
	for (int i=1;i<=t;i++)
	{
		for (int j=1;j<=n;j++) 
			if(((item[j]<t)&&pp[t-item[j]][j-1])||item[j]==t)
				return 1;
			else
				if(pp[i][j-1]||(item[j]<i)&&(pp[i-item[j]][j-1])||item[j]==i)
					pp[i][j]=1;
		    else
				pp[i][j]=0;
	}
	return 0;
}


void main()
{
	bag_problem();
}