题目 1917: 蓝桥杯-快乐司机

题目描述:

"嘟嘟嘟嘟嘟嘟
喇叭响
我是汽车小司机
我是小司机
我为祖国运输忙
运输忙"
这是儿歌“快乐的小司机”。话说现在当司机光有红心不行，还要多拉快跑。多拉不是超载，是要让所载货物价值最大，特别是在当前油价日新月异的时候。司机所拉货物为散货，如大米、面粉、沙石、泥土......
现在知道了汽车核载重量为w，可供选择的物品的数量n。每个物品的重量为gi,价值为pi。求汽车可装载的最大价值。（n<10000,w<10000,0<gi<=100,0<=pi<=100)

代码:

package lanqiao;
 
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); //数量
        int w = sc.nextInt(); //载重
        double[] gi = new double[n]; //重量
        double[] pi = new double[n]; //价值
        double[] arr = new double[n];
        for(int i = 0;i < pi.length;i ++)
        {
            gi[i] = sc.nextDouble();
            pi[i] = sc.nextDouble();
            arr[i] = pi[i] / gi[i];
        }
 
        for(int i = 0;i < arr.length - 1;i ++)
        {
            for(int j = 0;j < arr.length - i - 1;j ++)
            {
                //排序
                if(arr[j]<arr[j+1]){
                    double g =gi[j];
                    gi[j]=gi[j+1];
                    gi[j+1]=g;
                    double p =pi[j];
                    pi[j]=pi[j+1];
                    pi[j+1]=p;
                    double a =arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=a;
                }
            }
        }
 
        double sum = 0;
        for(int i = 0;i < arr.length;i ++)
        {
            if(w >= gi[i]){
                sum += pi[i];
                w -= gi[i];
 
            }else{
                sum += w * arr[i];
                break;
            }
        }
        System.out.printf("%.1f",sum);
    }
}