背包动规.cpp

这是经典的背包问题

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

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

/*问题描述：
设有n件物品，重量分别为W1,W2,……Wn 和一个能装载总重量为T的背包。
问能否从n件物品种选择若干件恰好使它们的重量之和等于T。若能，则背包问题有解，否则无解。
*/ 

#include<iostream.h>
void main(){
	int i,j,n,T;
	int *w;
	bool *bag;//存储各个重量为i的背包是否有可能被装满，若是则bag[i]为true
	cout<<"请输入物品个数n:";
	cin>>n;
	w=new int[n];
	cout<<"请依次输入物品重量:";
	for(i=0;i<n;i++)
		cin>>w[i];
	cout<<"请输入总重量T:";
	cin>>T;
	bag=new bool[T];
	for(i=0;i<T;i++)
		bag[i]=0;
	/*
	每次考虑一件物品。
	第i件重量为w[i]的物品，可以凑出重量为w[i]的背包,可将bag[w[i]]设为true；
	假设已经得到可以凑出重量为t的背包，即bag[j]==true,那么也凑出重量为t+w[i]的背包，可将bag[j+w[i]]设为true
	*/
	for(i=0;i<n;i++){
		for(j=T;j>=1;j--)
			if(j+w[i]<=T && bag[j]==true)
				bag[j+w[i]]=true;
		bag[w[i]]=true;
	}

	if(bag[T]==true) cout<<"该背包问题有解！"<<endl;
	else cout<<"该背包问题无解！"<<endl;
}