贪心算法解决背包问题

问题描述：

给定 n 个物品和一个容量为 C 的背包，请给出物品装入背包的方案，使得背包中物品的总价值 M 最大，并满足：
1.每个物品 I 的重量为 wi，价值为 vi。
2.每个物品可拆分，背包中物品的总重量不能超过容量 C 。

实验要求：

程序要求：

1）先写排序算法 Rank()，本文中使用快速排序完成，再写贪心算法 Greedy()。
2）两个步骤需要单独定义在程序里，不写在主函数里。

贪心算法解背包问题的基本步骤：

1）计算每种物品单位重量的价值 Vi / Wi
2）依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。
3）若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。
4）依此策略一直进行下去，直到背包装满为止。

代码实现：

快速排序：

快速排序的实现主要部分是partition部分，partition是对数组针对某一个数（此处以 数组第一个元素为基础）来分区。注意参数列表中，index是设定的记录交换的数据，即在数组中数据交换位置的时候，用index数组来记录交换信息，等后续用index数组可以遍历到交换完位置的数据。

int Partition(double arr[],int index [], int left,int right){
int i=left, j=right;
double x = arr[left];
while(i!=j){
	while(arr[j]>=x&&i<j) j--;
	while(arr[i]<=x&&i<j) i++;
	if(i>=j) break;
	swap(arr[i],arr[j]);
	swap(index[i],index[j]);
}
swap(arr[left],arr[i]);
swap(index[left],index[i]);

return i;
} 

void rank(double arr[],int index[],int left,int right){
	if(left<right){
		int q=Partition(arr,index,left,right);
		rank(arr,index,left,q-1);
		rank(arr,index,q+1,right);
	}
	else return ;
	
}

贪心算法：

贪心算法的核心逻辑为每次都进行最优的选择。在此处注意处理当背包恰好可以放下一个物品时，最好的逻辑选择是不进入做除法的操作，在for循环内部实现。

void Greedy(int n, double c, double w[], int b[], double x[]){
	int i;
	for(i=n-1;i>=0;i--){
		if(w[b[i]-1]>c) break;
		x[b[i]-1]=1;
		c-=w[b[i]-1];
	}
	if(i>=-1&&c>0) x[b[i]-1]=c/w[b[i]-1];
}

main函数测试：

运行前需要创建文件input.txt,写入读取的数据，同时创建output.txt文件，存放输出结果。

int main(){
	ifstream input("input.txt");//打开输入文件 
	if(!input)cout<<"The file can not open!!"<<endl;//文件打开失败 
	int n=0;
	double c;
	input>>c;//读入背包容量 
	double index[100],w[100],v[100];//定义索引数组，物品质量数组，物品价值数组 
	while(!input.eof())
	{
		input>>index[n]>>w[n]>>v[n];//按照顺序一次读取ID，物品价值，物品质量
		n++;
	}

	double totalvalue;
	double a[n],x[n];
	int b[n];
	for(int i=0;i<n;i++)x[i]=0;
	for(int i =0;i<n;i++){
		a[i]=v[i]/w[i];
		b[i]=i+1;
	}

	rank(a,b,0,n-1);
	Greedy(n,c,w,b,x);
	cout<<"The result is in the output.txt!"<<endl;
	ofstream output;
	output.open("output.txt");
	if(!output)cout<<"The file can not be open!!"<<endl; 
	for(int i=0;i<n;i++)
	{
		totalvalue+=v[i]*x[i];
	}
	output<<totalvalue<<endl;
	for(int i=0;i<n;i++)
	{
		output<<i+1<<"\t"<<x[i]*w[i]<<"\t"<<v[i]*x[i]<<"\t";
		output<<endl;
	}
	
} 

运行结果

实验总结：

贪心算法可以解决背包问题，而不能解决0-1背包问题。贪心算法的核心思想是每次都做最优选择，因此在进行贪心算法的时候，首先需要考虑数据按照什么标准排序，贪心的选择按照排序进行，每次选择最优结果，选择后，问题规模下降。因此，贪心算法是自顶向下的算法。