package demo1;



/**
 * 按照单位价值最高来计算
 * 贪心算法解决 背包问题 非0/1背包
 * @author Administrator
 *
 */
public class Knapsack {

	private float m; // 背包容量
	private float[] v; // 三个物品的价值
	private float[] w; // 三个物品的质量
	private float[] x; // 物品在背包中占的比例
	private int n; // 物品个数
	double[] p_w_v; // 每个物品的单位重量价值
	
	public static void main(String[] args) throws Exception {
		Knapsack ksp = new Knapsack();
		/*ksp.sort(ksp.n, ksp.v, ksp.w);
		System.out.println("w：");
		for (int i = 0; i < ksp.w.length; i++) {
			System.out.print(ksp.w[i] + " ");
		}
		System.out.println();
		System.out.println("v：");
		for (int i = 0; i < ksp.v.length; i++) {
			System.out.print(ksp.v[i] + " ");
		}*/
		ksp.knapsack();
	}
	
	public Knapsack() {
		this.m = 50.0f; // 背包容量为50
		this.v = new float[] { 60.0f, 120.0f, 50.0f }; // 三个物品的价值分别为60,120,100
		this.w = new float[] { 10.0f, 30.0f, 20.0f }; // 三个物品的质量分别是10,30,20
		this.x = new float[3]; // 往背包装东西的比例
		this.n = 3; // 三个物品
		this.p_w_v = new double[n]; // 每个物品的单位重量价值
	}

	// 对物品的单位重量价值进行排序
	public void sort(int n, float[] v, float[] w) throws Exception {
		//计算物品重量平均价值
		for (int i = 0; i < n; i++) {
			p_w_v[i] = v[i] / w[i];
		}
		System.out.println("单位重量价值：");
		print(p_w_v);
		System.out.println("");
		insertSort(p_w_v, w, v);
		print(p_w_v);
	}

	// 打印输出数组
	public void print(double a[]) {
		int len = a.length;
		for (int i = 0; i < len; i++) {
			System.out.print(a[i] + " ");
		}
	}
	
	// 打印输出数组
	public void print(String str) {
		System.out.println(str);
	}

	/**
	 * 从大到小排序：根据单位重量的价值，把质量和价值从大到小排序
	 * 
	 * @param a  每个物品的单位重量价值
	 * @param b  三个物品的质量分别是10,30,20
	 * @param c   三个物品的价值分别为60,120,100
	 */
	public void insertSort(double[] a, float[] b, float[] c) {// 排序静态函数，实现排序功能
		int len = a.length;// 获得数组长度
		double temp;// 临时变量，用于交换值
		float w_temp;
		float v_temp;
		//  从大到小排序
		for (int i = 0; i < len - 1; i++) { 
			for (int j = 0; j < len - 1 - i; j++) {
				if (a[j + 1] > a[j]) { // 如果后一下值比前一个值大，则交换两个值的大小，

					temp = a[j + 1]; 
					w_temp = w[j + 1];
					v_temp = v[j + 1];

					a[j + 1] = a[j];
					w[j + 1] = w[j];
					v[j + 1] = v[j];

					w[j] = w_temp;
					v[j] = v_temp;
					a[j] = temp;
				}
			}
		}
	}

	// 贪心算法核心思想
	public void knapsack() throws Exception {
		sort(n, v, w);
		int i;
		for (i = 0; i < n; i++) {
			x[i] = 0;
		}
		//重量
		float c = m;
		//遍历物品数目
		for (i = 0; i < n; i++) {
			//大于剩余重量，退出循环
			if (w[i] > c) {
				break;
			}
			//i物品，100%放入背包里
			x[i] = 1;
			//剩余的重量
			c -= w[i];
		}
		//计算超重的那个物品，占比例
		if (i < n) {
			x[i] = c / w[i];
		}
		System.out.println();
		print("物品一可以装入的比例: " + x[0]);
		print("物品二可以装入的比例: " + x[1]);
		print("物品三可以装入的比例: " + x[2]);
		print("可以装入的最大价值为: " + (x[0] * v[0] + x[1] * v[1] + x[2] * v[2]));
		print("可以装入的最大重量为" + (x[0] * w[0] + x[1] * w[1] + x[2] * w[2]));
	}
}