bag2.cpp

这是经典的背包问题

// 我真诚地保证：
// 我自己独立地完成了整个程序从分析、设计到编码的所有工作。
// 如果在上述过程中，我遇到了什么困难而求教于人，那么，我将在程序实习报告中
// 详细地列举我所遇到的问题，以及别人给我的提示。
// 我的程序里中凡是引用到其他程序或文档之处，
// 例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段,
// 我都已经在程序的注释里很清楚地注明了引用的出处。
// 我从未没抄袭过别人的程序，也没有盗用别人的程序，
// 不管是修改式的抄袭还是原封不动的抄袭。
// 我编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转。
// 学生：朱诗雄

/*
	文件名称：	bag
	项目名称：	背包问题
	创建者：	朱诗雄
	文件中的函数名称和简单功能描述：
		void bag(int *w,int n,int t) 给出n个背包，重量存储在w数组里，总重量为t，求出最小剩余空间best。

	输入格式：第一行输入背包数目n，第二行输入这n个背包的重量，第三行输入总重量t。
	例：
	5
	1 5 3 8 5
	7
	输出：
	one of answers is:6.
*/
#include<iostream>
using namespace std;

//求背包问题的递归函数
void bag(int *w,int n,int t);

static int best;			//存储最小剩余空间

int main()
{
	int n;					//背包数量
	cin>>n;
	int *w;
	w=new int [n];
	for(int i=0;i<n;i++)
		cin>>w[i];			//输入背包重量
	int t;					//总重量T		
	cin>>t;	
	cout<<"the best answer is:";
	best=t;
	bag(w,n,t);
	cout<<t-best<<endl;		//输出最多可放入的重量
	return 0;
}

void bag(int *w,int n,int t)
{
	if(t<best) best=t;
	if(n>=1)
	{
		if(t>=w[n-1]) bag(w,n-1,t-w[n-1]);
		bag(w,n-1,t);
	}
}