背包问题3.cpp

这是经典的背包问题

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

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

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

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

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

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

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

学号：00548250 
姓名：卞超轶

*/

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

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

int compare(const void *a, const void *b)         //qsort函数使用
{
	double temp = ((Goods*)b) -> perv - ((Goods*)a) -> perv;
	if (temp > 0)
		return 1;
	if (temp < 0)
		return -1;
	return 0;
}

void main()
{
	int t, n;
	cout << "请输入背包的载重（必须为整数，否则报错）：";
	cin >> t;
	assert(t > 0);      //背包载重大于零
	cout << "请输入商品的种数：";
	cin >> n;
	assert(n > 0);      //商品种数大于零
	
	Goods *a;
	a = new Goods[n];
	assert(a != NULL);

	int i;
	cout << "请依次输入各种商品的总重量和总价值（用空格分开，同时必须为整数，否则报错）：\n";
	for (i = 0; i < n; i++)
	{
		cin >> a[i].weight;
		assert(a[i].weight > 0);   //商品总重量大于零
	    cin >> a[i].value;
		assert(a[i].value > 0);    //商品总价值大于零
		a[i].perv = double(a[i].value) / a[i].weight;     //计算单位价值
	}

	qsort(a, n, sizeof(Goods), compare);   //按照商品单位价值降序排序

	double max = 0;
	for (i = 0; i < n; i++)
		if (a[i].weight <= t)        //商品总重量不超过背包剩余载重，则全取
		{
			t -= a[i].weight;
			max += a[i].value;
		}
		else                       //否则尽可能多取
		{
			max += a[i].perv * t;
			break;
		}
	
	cout << "能取得的最大价值（保留两位小数）：";
	cout << setiosflags(ios::fixed);
	cout << setprecision(2);
	cout << max << endl;
	
	delete[]a;
}