首页 > 代码库 > 贪婪法——————贪心算法

贪婪法——————贪心算法

华信清明节放假。所以不用去上课。而我又不想出去,所以就用了一点时间去研究算法。

我今天開始看王晓华写的《算法的乐趣》,把它当做教材。

看到贪心算法,由于大一的时候C语言没学好,所以作者写的C实现代码不是看得非常懂。可是基本思想还是可以掌握的。


接下来我总结一下我今天学到的贪心算法:

贪心算法是寻找最优解问题的经常用法。

基本思想是分三个步骤:

1.建立对问题精确描写叙述的数学模型,包货定义最优解的模型。

2.将问题分成一系列的子问题。同一时候定义子问题的最优解结构。

3.应用贪心算法原则能够确定每一个子问题的局部最优解。并依据最优解模型,用子问题的局部最优解堆叠出全局最优解。


然后我用java实现了书上贪婪法的样例:0-1背包问题

这是贪婪法的一个经典案例。有N件物品和一个承重C的背包,每件物品重量wi,价值pi,求解将那几件物品放入背包价值最大而又不超过负重。

书上举了一个样例:物品重量{35,30,60,50,40,10,25}

物品价值{10,40,30,50,35,40,30}

策略一:取最小重量的包负重140,价值155

策略二:取最大价值的包负重130。价值165

策略三:取价值密度最大的包负重150,价值170

然后作者给了C语言的策略一的实现方法。


我不太看得懂C,可是我看了几次作者的思想。自己渐渐也有点思路了。

于是我就用java自己实现了贪心算法,当中策略三这里卡了有半个小时了。原因是算法出了问题。

算法这一块还是有一定难度的,特别考验逻辑思维。

我认为一个算法仅仅要知道了思想,接下来实现的话。不管用C还是用java,都是一样的。《数学之美》作者吴军提到过文字仅仅是一种载体,本质是要传达一种信息思想。中文、英文甚至是机器语言都是一样的,当中不一样的仅仅是编码方式的不同而已。


接下来是我实现的代码,代码这一块,小小的算法也搞了我两个多小时。理清的逻辑。思路就清晰了。

当中遇到最大的问题是:我再取价值密度最大的物品的时候,最后一个价值密度最大的物品加上后就超出了负重。所以跳出了循环,死活加不上那个35负重的包。那里就卡了我将近半个小时。另一个地方卡了我20分钟,就是float转型的问题,我要定义一个float型的价值密度数据。然后比較,还要又一次创建一个比較函数。还要再运行逻辑语句的时候强转,还好我思路比較清晰,不然就晕头转向,解决不了问题了。

哈哈,我自己攻克了不少问题,看来我还是挺聪明的嘛技术分享


好了不废话了。以下是我的測试图:

技术分享


上面那一张是由測试输出的图,以下的是没有的:

技术分享


这也是我头一次听说价值密度这个概念。。。。。。

以下是我用java实现的代码:

分为三个类:先是主类

package 贪心算法;

import java.util.ArrayList;
import java.util.Vector;

public class Greedy {
	
		//有7个包:重量{35,30,60,50,40,10,25}
		//7个包的:价值{10,40,30,50,35,40,30}
	public static int[] strWeight = {35,30,60,50,40,10,25};
	public static int[] strValue = http://www.mamicode.com/{10,40,30,50,35,40,30};>算法实现类:

package 贪心算法;

import java.util.ArrayList;

import javax.swing.plaf.synth.SynthSpinnerUI;

public class Choice {
	public static final int biggestWeight = 150;
	public static void minWeight(){//选择重量最少的包
		int weight = 0;
		int value = http://www.mamicode.com/0;>
最后一个是工具类:

package 贪心算法;

import java.util.ArrayList;

public class Tool {
	public static int getMix(ArrayList list){//获取队列中的最小值
		int index = 0;
		for(int i=0;i<list.size();i++){
			if( (int)list.get(i)<(int)list.get(index) ){
				index = i;
			}
		}
		return index;
	}
	public static int getMax(ArrayList list){//获取队列中的最大值
		int index = 0;
		for(int i=0;i<list.size();i++){
			if( (int)list.get(i)>(int)list.get(index) ){
				index = i;
			}
		}
		return index;
	}
	
	public static int getfloatListMax(ArrayList list){//获取队列中的最大值
		int index = 0;
		for(int i=0;i<list.size();i++){
			if( (float)list.get(i)>(float)list.get(index) ){
				index = i;
			}
		}
		return index;
	}
}

一步一个脚印,慢慢来。技术分享

贪婪法——————贪心算法