bag1.cpp

这是经典的背包问题

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

/*
	文件名称：	bag
	项目名称：	背包问题
	创建者：	朱诗雄
	文件中的函数名称和简单功能描述：
		int bag(int *w,int n,int t) 给出n个背包，重量存储在w数组里，总重量为t，判断是否有解

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

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

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<<"one of answers is:";
	if(bag(w,n,t)==0) cout<<"no answer.";
	cout<<endl;
	return 0;
}

int bag(int *w,int n,int t)
{
	int i;
	for(i=n-1;i>=0;i--)			
		if((t-w[i])>=0)
		{
			if((t-w[i])==0 || bag(w,i,t-w[i])==1)  //背包问题有解的条件
			{
				cout<<w[i]<<' ';		//输出一个可行解
				return 1;
			}
		}
	return 0;
}