bag3.cpp

这是经典的背包问题

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

/*
	文件名称：	bag
	项目名称：	背包问题
	创建者：	朱诗雄

	输入格式：第一行输入背包数目n，接下来每一行输入这n个背包的重量和价值，最后一行输入总重量t。
	例：
	2
	5 56
	3 56
	4
	输出：
	the best answer is:3
	the max value is:56
*/
#include<iostream>
using namespace std;

int main()
{
	int n;					//背包数量
	cin>>n;
	int *w,*v;
	w=new int [n];
	v=new int [n];
	for(int i=0;i<n;i++)
		cin>>w[i]>>v[i];			//输入背包重量和价值
	int t;					//总重量T		
	cin>>t;	
	int num=1;
	for(i=0;i<n;i++)		//num用来算2的n次方
		num*=2;
	int k,l,value,weight,vmax=0;
//value是总价值，weight是总重量,vmax是满足题意的最大总价值,j是满足题意的最优方案
	for(int j=0;j<num;j++)
	{
		value=0;weight=0;k=j;
		for(int i=0;i<n;i++)
		{
			weight=weight+(k%2)*w[i];
			value=value+(k%2)*v[i];
			k=k/2;
		}
		if( (weight<=t) && (value>vmax) )	//总重量小于t，总价值大于vmax，这方案是比前面更好的方案
		{
			vmax=value;l=j;
		}
	}
	cout<<"the best answer is";
	for(i=0;i<n;i++,l=l/2)
		if(l%2==1) cout<<w[i]<<' ';		//输出最优方案
	cout<<endl;
	cout<<"the max value is:"<<vmax<<endl;		//输出满足题意的最大总价值
	return 0;
}