五种常见算法之贪心算法

贪心算法

贪心算法：贪心算法总是做出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。

贪心算法基本思路：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的求的更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。

贪心算法存在的问题：
1.不能保证求的最后解是最佳的。
2.不能用来求最大或最小解问题。
3.只能求满足某些约束条件的可行解的范围。

贪心算法的基本要求：
1.贪心选择性质：指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。
2.具有最优子结构性质：一个问题的最优解包含其子问题的最优解。


贪心算法解决背包问题：

物品类：Goods

package com.greed.yy;

public class Goods {
	//物体的重量
	private double w;
	//物体的价值
	private double v;
	//物体的单位价值
	private double p;
	
	public Goods(double w,double v){
		this.w = w;
		this.v = v;
		this.p = v/w;
	}

	public double getW() {
		return w;
	}

	public void setW(double w) {
		this.w = w;
	}

	public double getV() {
		return v;
	}

	public void setV(double v) {
		this.v = v;
	}

	public double getP() {
		return p;
	}

	public void setP(double p) {
		this.p = p;
	}
	
	
}

//主类：

package com.greed.yy;

/**
 * 用贪心算法解决背包问题
 * 
 * @author yuyang_csu
 *@data 2013-4-9
 */
public class Package {
	// 物品个数
	private int n;
	// 声明背包容量的数组
	private double c;
	// 声明储存物品的数组
	private Goods[] goods;

	public Package(int n, Goods[] goods, double c) {
		this.n = n;
		this.goods = goods;
		this.c = c;
	}

	// 对每个物品的单位价值进行排序
	public Goods[] sort() {
		Goods[] p = new Goods[goods.length];
		for (int i = 0; i < p.length; i++) {
			p[i] = goods[i];
		}

		for (int i = 1; i < p.length; i++) {
			Goods tmp = p[i];
			for (int j = i; j >= 1 && p[j].getP() > p[j - 1].getP(); j--) {
				p[j] = p[j - 1];
				p[j - 1] = tmp;
			}
		}
		return p;
	}

	// 装包
	public double knapsack() {
		double total = 0;
		Goods[] g = sort();
		for (int i = 0; i < g.length; i++) {
			double w = g[i].getW();
			if(w>c && c!=0){
				total+=c*g[i].getP();
				c=0;
			}else{
				c-=w;
				total+=g[i].getV();
			}
		}
		return total;
	}
	
	public static void main(String[] args) {
		Goods []goods = {new Goods(10,60),new Goods(20,100),new Goods(30,120)};
		Package p = new Package(3,goods,50);
		System.out.println(p.knapsack());
	}

}