greedy_algorithm.java

01背包四种算法实现(java版)

/*
 * Greedy_Algorithm.java
 *
 * Created on 2007年6月3日, 下午4:30
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package sunfa;

/**
 *
 * @author Administrator
 */
import java.util.*;

public class Greedy_Algorithm {
        static GreedyElement dd[];
        static int  CurrentV ;
        static int CurrentC;
        static StringBuffer stb= new StringBuffer();
	public static int knapasck(int c, int[] w, int[] v, int[] x) {
		int n = v.length;
		GreedyElement d [] = new GreedyElement[n];
		for(int i = 0 ;i< n; i++)
		{
			d[i]=new GreedyElement(w[i],v[i],i+1);
		}
		Arrays.sort(d);
                dd =d;
		for(int i = 0; i<d.length ;i++)
		{
			System.out.println("重量  " +d[i].ww+ "单位价值"+d[i].wv);
		}
		int i = 0;
		int MaxV2 = 0;
		for(i=0;i<n;i++)
			x[i] = 0;
		for(i=0;i<n;i++)
		{	
			if(d[i].ww>c)
				break;
			else
			{
				x[i] = d[i].tag; //x【】中存的是原元素的序号
				MaxV2 = MaxV2+d[i].value;
				c = c -d[i].ww;
                                CurrentC =c ;
                                 stb.append("选择第" + d[i].tag + "个当前价值:"+MaxV2+ "剩余容量:"+c+"\n");
			}
		}
		return MaxV2;
	}
}
 class GreedyElement implements Comparable{
	int ww;
	int value;
	double wv;
	int  tag;
	public GreedyElement(int w ,int vv ,int tag)
	{
		this.tag = tag;
		this.ww = w;
		this.value = vv;	
		wv = (double)vv/w;
	}
	public int compareTo(Object x)
	{
		GreedyElement temp = (GreedyElement)x;
		double rate = (double)ww/value;
		double temprate = (double)temp.ww/temp.value;
		if(rate<temprate)
			return -1;
		if(rate==temprate)
			return 0;
		else
		return 1;
	}
}