greedybag.cpp

贪心算法求背包问题,分别求出了三种标准1. 按效益值由大到小取物品. 2. 按重量值由小到大取物品 3.按比值pi/wi的值由大到小取物品 其中第3种是最优解

#include<iostream>
using namespace std;
#define M 120
#define N 10

float p[] = {50,60,70,80,90,80,70,60,50,40};
float w[] = {17,30,25,41,80,70,64,56,47,38};
float pw[N];
float x[N];
float result[N];

void change(float array[], int i, int j)
{	
	swap(array[i], array[j]);
	if(x != array)  swap(x[i], x[j]);
	if(pw != array)	swap(pw[i], pw[j]);
	if(w  != array) swap(w[i], w[j]);
	if(p != array) swap(p[i], p[j]);
}

void swap(float& a, float& b)
{
	float temp = a;
	a = b;
	b = temp;
}

void sort(float array[], bool down)
{
	for(int i=0; i<N; i++)
		for(int j=i+1; j<N; j++)		
			if(down && array[i] < array[j]) 
				change(array, i, j);
			else if(!down && array[i] > array[j])
				change(array, i, j);
			
}

void run()
{
	int sum = 0;
	for(int i=0; i<N; i++)
	{
		if((sum + w[i]) <= M)
		{		
			sum += w[i];
			result[i] = 1;
		}
		else
		{
			result[i] = (float)(M - sum) / w[i];
			break;
		}
	}
}

void showResult()
{
	float re = 0;
	
	for(int i=0; i<N; i++)
	{
	    re += (float)p[i] * result[i];
		cout<<"第"<<x[i] + 1<<"种物品的取值为:"<<result[i]<<endl;
	}
	cout<<"总效益:"<<re<<endl<<endl;
}

void init()
{
	for(int i=0; i<N; i++)
	{
		pw[i] = (float)p[i]/w[i];
		x[i] = i;
		result[i] = 0;
	}
}

int main()
{
	init();
    sort(p, true);	
	run();
	cout<<"按效益值由大到小取物品"<<endl<<endl;
	showResult();
	
	sort(w, false);
	run();
	cout<<"按重量值由小到大取物品"<<endl<<endl;
	showResult();		

	sort(pw, true);	
	run();
	cout<<"按比值pi/wi的值由大到小取物品"<<endl<<endl;
	showResult();
	
	return 0;
}