背包递归.cpp

这是经典的背包问题

// 我真诚地保证： 
// 我自己独立地完成了整个程序从分析、设计到编码的所有工作。
// 如果在上述过程中，我遇到了什么困难而求教于人，那么，我将在程序实习报告中
// 详细地列举我所遇到的问题，以及别人给我的提示。
// 我从未抄袭过别人的程序，也没有盗用别人的程序，
// 不管是修改式的抄袭还是原封不动的抄袭。
// 我编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转。
// 学生：韦春阳

//程序名称：背包递归
//程序目的：背包问题的递归实现
//创建者：韦春阳
//创建时间：2006年9月21日

/*问题描述：
设有n件物品，重量分别为W1,W2,……Wn 和一个能装载总重量为T的背包。
问能否从n件物品种选择若干件恰好使它们的重量之和等于T。若能，则背包问题有解，否则无解。
*/    
  
#include<iostream.h>
int countWeight(int,int,int*,int);//递归函数
void main(){
	int i,n,T;
	int *w;
	cout<<"请输入物品个数n:";
	cin>>n;
	w=new int[n];
	cout<<"请依次输入物品重量:";
	for(i=0;i<n;i++)
		cin>>w[i];
	cout<<"请输入总重量T:";
	cin>>T;
	if(countWeight(0,T,w,n)>0) cout<<"该背包问题有解！"<<endl;
	else cout<<"该背包问题无解"<<endl;
}
int countWeight(int item,int bag,int *w,int n)

//函数返回值:重量为bag的背包在已经考虑了前item个背包装或不装的情况下，还能有多少种情况被装满
//函数参数中：item为剩余没有考虑放或不放过的物品，bag为背包的剩余重量，w为存储重量的数组，n为物品的总数

{
	/*
	三个出口：
	当背包已经被装满，即没有剩余的情况下，bag==0，跳出，返回函数值1；
	当背包中数量超过能装的数量，即剩余小于0，bag<0，跳出，返回函数值0；
	当所有物品都被考虑过装或不装，即item==n，跳出返回0。
	*/
	if(bag==0)//出口1
		return 1;
	if(bag<0)//出口2
		return 0;
	if(item==n)//出口3
		return 0;
	int i,sum=0;
	for(i=item;i<n;i++)//递归过程：
		sum+=countWeight(i+1,bag-w[i],w,n);	
	return sum;
}