博客

实验目的

对特定的算法问题，设计多种不同的贪心策略，对比各贪心策略的执行结果，从中得到该问题的近似最优解。

实验内容

设计多种贪心策略，对比结果，得到0-1背包问题的近似最优解。

0-1背包问题

给定n个物品和一个容量为C的背包，物品i的重量是wi，其价值是vi，0-1背包问题要求从这n个物品中，选择装入背包的最优组合（物品不可以分割），使得装入背包中的物品的总价值最大。

实验原理

对0-1背包问题，可以设计多种贪心策略，如：

重量最轻的物品优先的贪心策略。

价值最大的物品优先的贪心策略。

单位价值最大的物品优先的贪心策略。

随机选择物品的贪心策略。

无法数学证明某一种策略的最优性，因此使用贪心法求解0-1背包问题时，必须尽可能多地枚举各种贪心策略，并从各种贪心策略的运行结果中，找出问题的近似最优解。

#include <bits/stdc++.h>
using namespace std;
struct node
{
	double v;//价值
	double w;//重量
} wu[100] ;
bool cmp1(node a,node b)//重量
{
	if(a.w==b.w)
		return a.v>b.v;
	return a.w<b.w;
}
bool cmp2(node a ,node b)//价值
{
	if(a.v==b.v)
		return a.w<b.w;
	return a.v>b.v;
}
bool cmp3(node a,node b)// 单位价值
{
	if((a.v/a.w)==(b.v/b.w))
		return a.w<b.w;
	return (a.v/a.w)>(b.v/b.w);
}
int fun1(int n,int c)
{
	sort(wu,wu+n,cmp1);
	int value=0;
	for(int i=0; i<n; i++)
	{
		if(c>=wu[i].w)
		{
			c-=wu[i].w;
			value+=wu[i].v;
		}
	}
	return value;
}
int fun2(int n,int c)
{
	sort(wu,wu+n,cmp2);
	int value=0;
	for(int i=0; i<n; i++)
	{
		if(c>=wu[i].w)
		{
			c-=wu[i].w;
			value+=wu[i].v;
		}
	}
	return value;
}
int fun3(int n,int c)
{
	sort(wu,wu+n,cmp3);
	int value=0;
	for(int i=0; i<n; i++)
	{
		if(c>=wu[i].w)
		{
			c-=wu[i].w;
			value+=wu[i].v;
		}
	}
	return value;
}
int random(int n,int c)
{
	int ans=-1,m=1000;
	int flag,b[110];
	while(m--)
	{
		int flag2=0,value=0;
		for(int i=0; i<n; i++)
		{
			b[i]=1;
		}
		while(1)
		{
			flag = rand() % n;
			if(b[flag]!=0)
			{
				if(flag2+wu[flag].w<=c)
				{
					flag2+=wu[flag].w;
					b[flag]=0;
					value+=wu[flag].v;
				}
			}
			else
			{
				break;
			}
		}
		if(value>ans)
		{
			ans=value;
		}
	}
	return ans;
}
int main()
{
	int n,c;//n个物品，c的容量
	cin>>n>>c;
	for(int i=0; i<n; i++)
		cin>>wu[i].w;
	for(int j=0; j<n; j++)
		cin>>wu[j].v;
	cout<<"优先放重量最小的答案：";
	cout<<fun1(n,c)<<endl;
	cout<<"优先放价值最大的答案：";
	cout<<fun2(n,c)<<endl;
	cout<<"先放性价比最大的答案：";
	cout<<fun3(n,c)<<endl;
	cout<<"随机1000次最大的答案：";
	cout<<random(n,c)<<endl;
	return 0;
}