alefhidalgo

MilkmanProblem

Jun 20th, 2011
994
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.Scanner;
  2.  
  3. /**
  4.  * Tuenti Programming Contest
  5.  * Challenge 5: The Milkman Problem
  6.  * @author alefhidalgo [at] gmail [dot] com
  7.  */
  8. public class MilkmanProblem {
  9.  
  10.    
  11.     private int optimize(int[] ps, int[] bs, int c) {
  12.         int[] partialSol = new int[ps.length];
  13.         int[] optimSol = new int[ps.length];
  14.         int best = search(ps.length - 1, 0, c, 0, partialSol, optimSol, -1, ps,
  15.                 bs, c);
  16.         return best;
  17.     }
  18.  
  19.     private int search(int n_1, int i, int p, int b, int[] partialSol,
  20.             int[] optimSol, int best, int[] ps, int[] bs, int c) {
  21.         for (int k = 0; k <= 1; k++) {
  22.             if (k * ps[i] <= p) {
  23.                 partialSol[i] = k;
  24.                 int np = p - k * ps[i];
  25.                 int nb = b + k * bs[i];
  26.                 if (i == n_1) {
  27.                     if (nb > best) {
  28.                         best = nb;
  29.                         for (int j = 0; j < ps.length; j++)
  30.                             optimSol[j] = partialSol[j];
  31.                     }
  32.                 } else {
  33.                     best = search(n_1, i + 1, np, nb, partialSol, optimSol,
  34.                             best, ps, bs, c);
  35.                 }
  36.  
  37.             }
  38.         }
  39.         return best;
  40.     }
  41.     /**
  42.      * calculate
  43.      * @param calculatecowWeight
  44.      * @param cowMilkProduction
  45.      * @param truckWeight
  46.      * @return
  47.      */
  48.     public int calculate(String[] cowWeight, String[] cowMilkProduction, int truckWeight) {
  49.        int [] icowMilkProduction=new int[cowMilkProduction.length];
  50.        int [] icowWeight=new int[cowWeight.length];
  51.        for (int i = 0; i < cowWeight.length; i++) {
  52.            icowWeight[i]= Integer.parseInt(cowWeight[i]);
  53.        }
  54.        for (int i = 0; i < cowMilkProduction.length; i++) {
  55.            icowMilkProduction[i]= Integer.parseInt(cowMilkProduction[i]);
  56.        }
  57.        return optimize(icowWeight, icowMilkProduction,truckWeight);
  58.    }
  59.  
  60.    
  61.     public static void main(String args[]) {
  62.         MilkmanProblem milkmanProblem = new MilkmanProblem();
  63.         Scanner in = new Scanner(System.in);
  64.         Scanner lineScanner = null;
  65.         int truckWeight;
  66.         String[] cowWeight = null;
  67.         String[] cowMilkProduction = null;
  68.         while (in.hasNextLine()) {
  69.             lineScanner = new Scanner(in.nextLine());
  70.             lineScanner.next();
  71.             truckWeight = lineScanner.nextInt();
  72.             cowWeight = lineScanner.next().split(",");
  73.             cowMilkProduction = lineScanner.next().split(",");
  74.             System.out.println(milkmanProblem.calculate(cowWeight, cowMilkProduction, truckWeight));
  75.         }
  76.     }
  77. }
RAW Paste Data