fork download 
  1. import java.util.Arrays;
  2. import java.util.Scanner;
  3. import java.util.Comparator;
  4.  
  5. public class Main {
  6.     static class Item {
  7.         double ratio;
  8.         int weight;
  9.         int value;
  10.  
  11.         public Item(double ratio, int weight, int value) {
  12.             this.ratio = ratio;
  13.             this.weight = weight;
  14.             this.value = value;
  15.         }
  16.     }
  17.  
  18.     static class ItemComparator implements Comparator<Item> {
  19.         @Override
  20.         public int compare(Item a, Item b) {
  21.             // Sorts in descending order of ratio (a.ratio > b.ratio)
  22.             if (a.ratio < b.ratio) {
  23.                 return 1;
  24.             } else if (a.ratio > b.ratio) {
  25.                 return -1;
  26.             } else {
  27.                 return 0;
  28.             }
  29.         }
  30.     }
  31.  
  32.     public static void main(String[] args) {
  33.         Scanner scanner = new Scanner(System.in);
  34.  
  35.         int n = scanner.nextInt();
  36.         double W = scanner.nextInt();
  37.  
  38.         int[] weights = new int[n];
  39.         int[] values = new int[n];
  40.  
  41.         for (int i = 0; i < n; i++) {
  42.             weights[i] = scanner.nextInt();
  43.         }
  44.  
  45.         for (int i = 0; i < n; i++) {
  46.             values[i] = scanner.nextInt();
  47.         }
  48.  
  49.         Item[] items = new Item[n];
  50.  
  51.         for (int i = 0; i < n; i++) {
  52.             double ratio = (double) values[i] / weights[i];
  53.             items[i] = new Item(ratio, weights[i], values[i]);
  54.         }
  55.  
  56.         // Sort items by ratio in descending order
  57.         Arrays.sort(items, new ItemComparator());
  58.  
  59.         double totalValue = 0.0;
  60.         double remainingCapacity = W;
  61.  
  62.         for (int i = 0; i < n; i++) {
  63.             Item item = items[i];
  64.  
  65.             if (remainingCapacity >= item.weight) {
  66.                 totalValue += item.value;
  67.                 remainingCapacity -= item.weight;
  68.             } else {
  69.                 totalValue += item.ratio * remainingCapacity;
  70.                 break;
  71.             }
  72.         }
  73.  
  74.         System.out.printf("%.2f%n", totalValue);
  75.         scanner.close();
  76.     }
  77. }
Success #stdin #stdout 0.12s 56684KB
comments (?)
stdin 
3 30
15 30 45
60 100 120
stdout 
110.00
https://ideone.com/YnL65G
language:
Java (HotSpot 12)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!