背包问题2.cpp.bak

这是经典的背包问题

/*
我真诚地保证
我自己独立地完成了整个程序从分析、设计到编码的所有工作。

如果在上述过程中，我遇到了什么困难而求教于人，那么，我将在程序实习报告中
详细地列举我所遇到的问题，以及别人给我的提示。

我的程序里中凡是引用到其他程序或文档之处，

我都已经在程序的注释里很清楚地注明了引用的出处。

我从未抄袭过别人的程序，也没有盗用别人的程序，

不管是修改式的抄袭还是原封不动的抄袭。

我编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转。

学号：00548250 
姓名：卞超轶

*/

#include <iostream.h>
#include <assert.h>

struct Goods                  //定义商品记录类型
{
	int weight;        //重量
	int value;         //价值
};

void main()
{
	int t, m;
	cout << "请输入背包的载重（必须为整数，否则报错）：";
	cin >> t;
	assert(t > 0);       //背包载重大于零
	cout << "请输入商品的个数：";
	cin >> m;
	assert(m > 0);        //商品个数大于零
	
	Goods *a;
	a = new Goods[m+1];
	assert(a != NULL);
	int i, j;
	cout << "请依次输入各商品的重量和价值（用空格分开，同时必须为整数，否则报错）：\n";
	for (i = 1; i <= m; i++)
	{
		cin >> a[i].weight;
		assert(a[i].weight > 0);    //商品重量大于零
	    cin >>a[i].value;
		assert(a[i].value > 0);     //商品价值大于零
	}

	int **max;
	max = new int*[m+1];
	for (i = 0; i <= m; i++)
		max[i] = new int[t + 1];
	assert(max != NULL);
	for (i = 0; i <= m; i++)
		for (j = 0; j <= t; j++)
			max[i][j] = 0;          //申请动态数组并初始化，
		                            //max[i][j]表示只有前i个商品且背包载重为j时能取得的最大价值

	for (i = 1; i <= m; i++)
		for (j = 0; j <= t; j++)
		{
			if (j < a[i].weight)
				max[i][j] = max[i-1][j];
			else
			{
				if (max[i-1][j] > max[i-1][j-a[i].weight] + a[i].value)
					max[i][j] = max[i-1][j];
				else max[i][j] = max[i-1][j-a[i].weight] + a[i].value;
			}
		}
	
	cout << "能取得的最大价值为：" << max[m][t] << endl;
	
	delete[]a;
	delete[]max;
}