学步园

import java.util.Scanner;

//用贪心算法实现的背包问题
public class BagProblem ...{

    public static void main(String[] args) ...{
        
        Scanner input = new Scanner(System.in);
        int n = 0;
        System.out.println("please input the maxweight of bag");
        
        //定义背包的最大容量maxWeight
        Bag bag = null;
        if(input.hasNextInt()) ...{
            n = input.nextInt();
            bag = new Bag(n);
            System.out.println("please input the number of things");
        }
        
        //定义物品的数量num
        Thing[] things = null;
        int thingsNum = 0;
        if(input.hasNextInt()) ...{
            n = input.nextInt();
            thingsNum = n;
            things = new Thing[n];
            System.out.println("please input weight and value of thing " + 1);
        }
        
        //定义每个物品的重量weight, 价值value
        int i = 0;
        while(input.hasNextInt()) ...{
            int[] temp = new int[2];
            for(int j = 0; j < 2; j++)...{
                n = input.nextInt();
                temp[j] = n;
            }
            things[i] = new Thing(temp[0], temp[1]); 
            
            if(i < thingsNum - 1) ...{
                System.out.println("please input weight and value of thing " + (++i +1));
            }
            else break;
        }
        
        System.out.println(bag.getsMaxValue(things));
    
    }

}


//背包类
class Bag ...{
    //maxWeight:背包的最大容量
    double maxWeight;
    
    Bag(double mw) ...{
        maxWeight = mw;
    }
    
    public double getsMaxValue(Thing[] things) ...{
        int num = things.length;
        double[] weights = new double[num];
        double[] values = new double[num];
        
        for(int i = 0; i < num; i++) ...{
            weights[i] = things[i].weight;
            values[i] = things[i].value;
        }
        
        Thing[] thingsBeenSorted = new Thing[num];
        for(int i = 0; i < num; i++) ...{
            thingsBeenSorted[i] = new Thing(weights[i], values[i]); 
        }
        BubbleSort.bubbleSort(thingsBeenSorted);
        
        double maxValue = 0;
        int i;
        for(i = 0 ; i < num; i++) ...{
            if(thingsBeenSorted[i].weight > maxWeight) ...{break;}
            thingsBeenSorted[i].part = 1;
            maxValue += thingsBeenSorted[i].value;
            maxWeight -= thingsBeenSorted[i].weight;
        }
        if(i < num) ...{
            thingsBeenSorted[i].part = maxWeight/thingsBeenSorted[i].weight;
            return maxValue += thingsBeenSorted[i].part * thingsBeenSorted[i].value;
        }
        return -1;
    }
    
}


//物品类
class Thing implements Comparable ...{
    //weight:物品的重量, value:物品的价值, 
    //part:物品被装入背包的部分占自身总体部分的百分比, vPerw:value与weight的比值
    double weight, value, part, vPerw;
    
    Thing(double w, double v) ...{ //, double p
        weight = w;
        value = v;
        part = 0;
        vPerw = v/w;
    }

    public int compareTo(Object o) ...{
        if(vPerw > ((Thing)o).vPerw) ...{return 1;}
        if(vPerw < ((Thing)o).vPerw) ...{return -1;}
        return 0;
    }
    
}


//冒泡排序类(注意这里是按vPerw的大小降序排列的)
class BubbleSort ...{
    static void bubbleSort(Thing[] things) ...{
        Thing temp;
        for(int i = things.length - 1; i >= 1; i --) ...{
            for(int j = 0; j <= i - 1; j ++)    ...{
                if(things[j].compareTo(things[j+1]) < 0) ...{
                    temp = things[j];
                    things[j] = things[j+1];
                    things[j+1] = temp;
                }    
            }
        }    
    }
}