贪心算法之背包可拆

直接上代码：

package com.贪心算法;

import java.util.Iterator;
import java.util.Scanner;

public class Bag72 {
	public static void main(String[] args) {
		float[] price = new float[100];  //意见物品能产生的收益
		float[] weight = new float[100];  // 一件物品的重量
		float[] x = new float[100];       // 是否装入  0<=x<=1
		float allweight = 0 ,shenyuweight  ,allprice = 0 ;
		int i = 0;
		//allweight为背包总重量
		//，shenyuweight表示背包还可以装下的重量
		//allprice  总收益
		int count ;  //总的物品数量
		Scanner scanner = new Scanner(System.in);
		System.out.println("输入物品数量：");
		count = scanner.nextInt();
		System.out.println("输入背包总重量：");
		allweight = scanner.nextFloat();
		
		for ( i = 0; i <count; i++) {
			price[i] = scanner.nextFloat();
			weight[i] = scanner.nextFloat();
		}
		
		/*
		 * 求出一件物品的平均单位的价值 ： price[i]/weight[i] 再对平均价值排序    ,
		 * 变成了  price[i]*weight[i]<price[j]*weight[j]  冒泡排序  
		 * */
		for( i = 0;i < count - 1;i++){
			for (int j = i+1 ;  j < count; j++) {
				if(price[i]*weight[i]<price[j]*weight[j]){
					float temp = price[i]; price[i] = price[j] ;price[j] = temp;
					temp = weight[i] ;weight[i] = weight[j] ;weight[j] = temp;
				}
			}
		}
		shenyuweight = allweight ;  //初始背包剩余可以装入的重量为背包重量
		for( i = 0;i < count ;i++){   
			if(weight[i]>shenyuweight){  //直到不能装入退出循环
				break;
			}
			//贪心算法，将能装入的全部装入，整个装入。
			x[i] = 1 ;shenyuweight -= weight[i] ;allprice+=price[i] ;   
		}
		
		//如果可以装入，但是不能整个装入
		x[i] =(float)(shenyuweight/weight[i]);  //此时的x[i]接着上面的x[i]
		allprice = x[i]*price[i] ;
		
		for (i = 0;i < count ;i++) {
			if(x[i]<1){
				break;
			}else{
				System.out.println("装入的重量为："+weight[i]+"/t 价值为："+price[i]);
			}			
		}
		if(x[i]>0 && x[i] < 1){  //能装入，但不能整个装入
			System.out.println("装入的重量为："+x[i]*weight[i]+"\t 效益为："+price[i]*x[i]+"是原来的"+x[i]);
		}
		System.out.println("一共装入"+allweight+"\t 收益为"+allprice);
	}
}