背包问题.cpp

设有一个背包可以放入的物品重量最重为s

#include<iostream.h>

#include<stdlib.h>

 
int  knap (int s, int n, int w[])
{
	if (s == 0)
	{ return 1;}

	else if (s < 0 )
	{ return 0;}
	
	else if ( s > 0 && n < 1)
	{return 0;}
	
	else if (knap (s - w[n - 1], n - 1, w) == 1)
	{
		cout<<"包中有：第"<<n<<"个物品，质量为"<<w[n-1]<<endl;
		return (1);
	}
	else
		return (knap (s, n - 1, w));
}
 
 
void main ()
{
	int *w;
	int s = 0, n = 0, result = 0, i = 0;
	 cout<<"包中最多可装载的重量为：";	/*输入s */
	  cin>>s;
    if(s==0)
	{cout<<"此背包问题一定有解"<<endl;
	  exit(0);
	}
	 if (s < 0 )
	 {
		 cout<<"总质量不能为负数"<<endl;
	   exit(0);
	 }
	
	  cout<<"请输入n值： ";	/*输入n */
	  cin>>n; 
	  if ( s > 0 && n < 1)
	  {
		  cout<<"物品件数不能为负数"<<endl;
	    exit(0);
	  }
	w = new int[n];
	  cout<<"请输入这"<<n<<"个物品的质量:"<<endl;	/*输入重量 */
	for (i = 0; i < n; i++)
		cin>>w[i];
	result = knap (s, n, w);
	if (result == 0)
	  cout<<"此背包为题无解"<<endl;
	 
}