01背包递归.cpp

这是经典的背包问题

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

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

/*问题描述：
给定n种物品和一个背包，物品i的重量是Wi，其价值为Vi，背包的容量为T，
问如何选择装入背包的物品，使得装入背包的物品的总价值最大?
*/

#include<iostream.h>
int max=0;//全局变量，存储背包中能装该物品的最大价值
int *v;
int *w;
bool *take;//存储是否拿了该物品，若拿了则为true，否则为false
int n;
int dotake(int leftWeight,int Value)//返回值为在背包剩余的空间leftWeight中最多能装多少价值的东西
{
	int i,temp=0,cvalue=0;
	//	出口条件：如果所有的物品都被放到了包里或所有的物品都放不到背包所剩的空余重量中
	for(i=0;i<n;i++){
		if(take[i]==true||leftWeight<w[i])
			temp++;
	}
	if(temp==n) return Value;
	
	/*
	递归过程：
	1.如果第i件物品已经被放到背包中或是背包剩余的重量不足以盛下该物品，则跳过，考虑下一件物品
	2.否则假设取该物品，将take[i]设为true,
	用临时变量cvalue储存放该物品到背包中的情况下背包最多能装多少价值（dotake(leftWeight-w[i],Value+v[i])）
	用cvalue和全局变量max（之前得到的能装的最多价值）比较
	3.将take[i]设为false，回溯以进行不放该物品的情况的讨论。
	4.返回max(背包能装的最多价值)
	*/
	for(i=0;i<n;i++){
		if(take[i]==true||leftWeight<w[i]) continue;
		else{
			take[i]=true;
			cvalue=dotake(leftWeight-w[i],Value+v[i]);
			if(max<cvalue) max=cvalue;
			take[i]=false;//回溯
		}
	}
	return max;
}
void main(){
	int i,T;	
	cout<<"请输入物品个数n:";
	cin>>n;
	w=new int[n];
	v=new int[n];
	take=new bool[n];
	cout<<"请依次输入物品重量:";
	for(i=0;i<n;i++)
		cin>>w[i];
	cout<<"请依次输入物品价值:";
	for(i=0;i<n;i++)
		cin>>v[i];
	cout<<"请输入总重量T:";
	cin>>T;
	for(i=0;i<n;i++)
		take[i]=0;

	cout<<dotake(T,0)<<endl;
}