bag_2.cpp

这是经典的背包问题

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

////////////////////////////////////////////////////////////////////////////////
//背包问题二
//有价值分别为x1 x2 x3  x4  x5...xt每单位的金属y1 y2  y3  y4...yt 个单位且金属//可以分割
//有一个背包大小为t个单位
//求背包能装的金属的最大的价值
//////////////////////////////////////////////////////////////////////////
//贪心法
struct metal//金属的结构
{
	double value;//单位价值
	double volume;//体积
};

double cal_value();
int mycompare(const void * a,const void *b);

double cal_value()
{
	int n;
	double sum=0;
	double volume_left;

	cout<<"put in the number of kind of the metal and the total volume"<<endl;
	cin>>n>>volume_left;
	metal *pp=new metal[n];
    cout<<"put in each metal's value and volume"<<endl;
    for (int i=0;i<n;i++)
		cin>>pp[i].value>>pp[i].volume;
	qsort((void*)pp,n,sizeof(metal),mycompare);
	for (int j=0;j<n;j++)
	{
		if (pp[j].volume<volume_left)
		{
			sum+=pp[j].volume*pp[j].value;
			volume_left-=pp[j].volume;
		}
		else
		{
			sum+=pp[j].value*volume_left;
			break;
		}
	}
	delete [] pp;
	return sum;
}

int mycompare(const void * a,const void *b)
{
	if( ((metal*)a)->value<((metal*)b)->value )
		return 1;
	return 0;
}


void main()
{
	cal_value();
}