java吧 关注:1,246,489贴子:12,723,643
  • 5回复贴,共1

Java菜鸟求大神指导——算法提高快乐司机问题

取消只看楼主收藏回复

菜鸟一枚,会用的也少,做了两个小时还是90分,求大神指导


来自Android客户端1楼2016-02-11 22:33回复


    2楼2016-02-11 22:34
    回复
      求大神指导 啊


      3楼2016-02-11 22:37
      回复
        import java.util.Scanner;
        public class Main{
        public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int w = input.nextInt();
        int[] gList = new int[n];
        int[] pList = new int[n];
        double[] gp = new double[n];
        for(int i = 0; i < n; i++){
        gList[i] = input.nextInt();
        pList[i] = input.nextInt();
        gp[i] = (double)pList[i] / gList[i];
        }
        double sum = 0;
        for(int j = 0; j < n - 1; j++){
        double maxGp = gp[j];
        int maxG = gList[j], maxP = pList[j], index = j;
        for(int i = j + 1; i < n; i++){
        if(gp[i] > maxGp){
        maxGp = gp[i];
        maxG = gList[i];
        maxP = pList[i];
        index = i;
        }
        }
        gp[index] = gp[j];
        gp[j] = maxGp;
        gList[index] = gList[j];
        gList[j] = maxG;
        pList[index] = pList[j];
        pList[j] = maxP;
        if(gList[j] > w){
        sum += w * gp[j];
        break;
        }
        else if(gList[j] == w){
        sum += pList[j];
        break;
        }
        else if(gList[j] < w){
        w -= gList[j];
        sum += pList[j];
        }
        }
        System.out.println( (int)(sum * 10) / 10.0 );
        }
        }


        5楼2016-02-11 22:42
        回复
          原题也贴一下:
          问题描述  "嘟嘟嘟嘟嘟嘟
            喇叭响
            我是汽车小司机
            我是小司机
            我为祖国运输忙
            运输忙"
            这是儿歌“快乐的小司机”。话说现在当司机光有红心不行,还要多拉快跑。多拉不是超载,是要让所载货物价值最大,特别是在当前油价日新月异的时候。司机所拉货物为散货,如大米、面粉、沙石、泥土......
            现在知道了汽车核载重量为w,可供选择的物品的数量n。每个物品的重量为gi,价值为pi。求汽车可装载的最大价值。(n<10000,w<10000,0<gi<=100,0<=pi<=100)输入格式  输入第一行为由空格分开的两个整数n w
            第二行到第n+1行,每行有两个整数,由空格分开,分别表示gi和pi输出格式  最大价值(保留一位小数)样例输入
          5 36
          99 87
          68 36
          79 43
          75 94
          7 35样例输出71.3
          解释:
          先装第5号物品,得价值35,占用重量7
          再装第4号物品,得价值36.346,占用重量29
          最后保留一位小数,得71.3


          7楼2016-02-11 22:43
          回复
            做了两个小时,一直出错,不断调试,修改好几遍到了90分后就不会了,不知道错在哪里啊


            9楼2016-02-11 22:47
            回复