mgreedy3算法.cpp

来自「自己编写的」· C++ 代码 · 共 43 行

#include <iostream>
#include <algorithm>
using  namespace std;
const int N = 50;
typedef struct goods 
{
	int value;   // 物品价值
	int weigh;   // 物品重量
}Goods;

bool comp(Goods& a,Goods& b)
{
	return (a.value * 1.0)/a.weigh > (b.value*1.0)/b.weigh; // 价值密度可能为浮点数
}


int main()
{

	int n;      // 物品总数
	int W;      // 背包总重量
	Goods bagGoods[N]; 
	int i,j,t;
	scanf("%d%d",&n,&W);
	for(i = 0; i < n; i++)
		scanf("%d",&bagGoods[i].value);
	for(j = 0; j < n; j++)
		scanf("%d",&bagGoods[j].weigh);
	sort(bagGoods,bagGoods+n,comp);           // 按价值密度排序
	int w = W,count = 0;
	i  = 0;
	while(bagGoods[i].weigh <= w && i < n){
		w = w - bagGoods[i].weigh;
		count += bagGoods[i].value;
		i++;
	}
	int vmax = 0;
	for(j = 0; j < n; j++)
		if((bagGoods[j].value > vmax) && (bagGoods[j].weigh <= W))
			vmax = bagGoods[j].value;
	printf("%d\n",(count > vmax ? count:vmax));
	return 0;
}