bag_recursion.cpp

来自「这是经典的背包问题」· C++ 代码 · 共 43 行

#include<iostream.h>
////////////////////////////////////////////////////////////////////////////////
//用递归实现
int n;//number of items
int*item;//pointer to the items' array
int t;//total capability

bool bag_recursion_judge(int k,int t); //递归规划函数 有解返回1 否则 0
void bag_recursion();//输入数组等辅助工作//判断背包是否有解

////////////////////////////////////////////////////////////////////////////////
void bag_recursion()
{
	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=0;i<n;i++)
		cin>>item[i];
	if(bag_recursion_judge(0,t))
		cout<<"yes"<<endl;
	else
		cout<<"no"<<endl;
	delete [] item;
}


bool bag_recursion_judge(int k,int t)
{	
	if (t==0)
		return 1;
	if (k==n)
		return 0;
	if(t<0)
		return 0;
	return bag_recursion_judge(k+1,t-item[k])||bag_recursion_judge(k+1,t);
}


void main()
{
	bag_recursion();
}