01背包动规.cpp

这是经典的背包问题

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

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

/*问题描述：
给定n种物品和一个背包，物品i的重量是Wi，其价值为Vi，背包的容量为T，
问如何选择装入背包的物品，使得装入背包的物品的总价值最大?
*/
#include<iostream.h>
struct Item{
	int w,v;
};//存储物品性质（重量、价值）的结构

void main(){
	int i,j,n,T;
	int *best;//存储重量为i的空间最多能装价值多少的东西
	Item *item;
	cout<<"请输入物品个数n:";
	cin>>n;
	item=new Item[n];
	best=new int[n];
	cout<<"请依次输入物品重量:";
	for(i=0;i<n;i++)
		cin>>item[i].w;
	cout<<"请依次输入物品价值:";
	for(i=0;i<n;i++)
		cin>>item[i].v;
	cout<<"请输入总重量T:";
	cin>>T;
	for(i=0;i<n;i++)
		best[i]=0;
	/*
	先按没考虑这个物品之前的best考虑。
	如果一个重量为j的空间的最多装的价值，比刨去这个物品重量的重量空间能装的价值和这个物品的价值之和要小
	显然那么可以让刨去这个物品重量的重量空间能装的价值最多的情况在装上这个物品
	best[j]变为装了这个物品之前的重量为j-item[i].w的空间最多的价值与这个物品的价值之和
	*/
	for(i=0;i<n;i++){
		for(j=T;j>=item[i].w;j--){
			if(best[j]-best[j-item[i].w]<item[i].v)
				best[j]=best[j-item[i].w]+item[i].v;
		}
	}
	cout<<best[T];
}