背包问题-贪心算法-物品可分割

#include "stdafx.h"
#include "iostream"
#include <algorithm> 
#define NUM 100
using namespace std;

struct bag
{
	int w; //重量
	int v; //价值
	double c; //谓之，性价比
	int id;  //物品编号
	int x; //装入部分
}b[NUM];

struct bag2
{
	int w;
	int v;
	double c;
	int id;  //物品编号
	int x; //装入部分
};

bool cmp(bag a,bag b)
{
	return a.c>=b.c;
}

double knapsack(int n,bag a[],double c)
{
	double cleft=c;
	int i=0;
	double b=0;
	while (i<n&&a[i].w<cleft)
	{
		cleft-=a[i].w;
		b+=a[i].v;
		a[i].x=1.0;
		i++;
	}
	if(i<n){
		b+=1.0*a[i].v*cleft/a[i].w;
		a[i].x=cleft/a[i].w;
	}
	return b;
}


int _tmain(int argc, _TCHAR* argv[])
{
	int n;
	double c;
	cin>>c>>n;
	for(int i=0;i<n;i++)
	{
		cin>>b[i].w>>b[i].v;
		b[i].c=b[i].v/b[i].w;
		b[i].id=i;
		b[i].x=0;
	}
	
	sort(b,b+n,cmp);
	cout<<"最优解："<<knapsack(n,b,c)<<endl;
	cout<<"最优解向量："<<endl;
	for(int i=0;i<n;i++)
		if(b[i].x>0)
			cout<<i<<"->"<<b[i].x<<endl;
	system("pause");
	return 0;
}