package test;

import java.util.Arrays;
import java.util.List;
import java.util.Map;

/**
 * You are a renowned thief who has recently switched from stealing precious metals to stealing cakes
 * because of the insane profit margins. You end up hitting the jackpot,
 * breaking into the world's largest privately owned stock of cakes—the vault of the Queen of England.
 * While Queen Elizabeth has a limited number of types of cake, she has an unlimited supply of each type.
 *
 * Each type of cake has a weight and a value, stored in tuples with two positions:
 *
 *   An integer representing the weight of the cake in kilograms
 *   An integer representing the monetary value of the cake in British pounds
 *
 * For example:
 *
 *   # weighs 7 kilograms and has a value of 160 pounds
 *   (7, 160)
 *
 *   # weighs 3 kilograms and has a value of 90 pounds
 *   (3, 90)
 *
 * You brought a duffel bag that can hold limited weight,
 * and you want to make off with the most valuable haul possible.
 *
 * Write a function max_duffel_bag_value() that takes an array of cake tuples and a weight capacity,
 * and returns the maximum monetary value the duffel bag can hold.
 *
 * For example:
 *
 *   cake_tuples = [(7, 160), (3, 90), (2, 15)]
 *   capacity    = 20
 *
 *   max_duffel_bag_value(cake_tuples, capacity)
 *   # returns 555 (6 of the middle type of cake and 1 of the last type of cake)
 *
 * Weights and values may be any non-negative integer.
 * Yes, it's weird to think about cakes that weigh nothing or duffel bags that can't hold anything.
 * But we're not just super mastermind criminals—we're also meticulous about keeping our algorithms flexible and comprehensive.
 *
 * @author Silvino Barreiros (sbarreiros@sharaholic.com)
 */


public class test {
	  public static int max( Coin[] coins,  int capacity) {
		  /// find max density
		  List<Coin> lCoins = Arrays.asList(coins);
		  lCoins.sort(( Coin o1, Coin o2) -> o2.value/o2.weight - o1.value/o1.weight );
		  Coin[] dCoins = (Coin[]) lCoins.toArray();
		  int c = capacity;
		  int max2 = 0;
		  /// Starting take the most density
		  for( int i=0; i<dCoins.length; i++ ){
			  for( ; c>0; ) {
				  if( c >= dCoins[i].weight ) {
					  max2 += dCoins[i].value;
					  c -= dCoins[i].weight;
					  System.out.print( "coins[" + i + "] : (" + dCoins[i].weight + ", " + dCoins[i].value + "); \n");
				  }
				  else {
					  break;
				  }
			  }
		  }
		  
		  System.out.print("max2 = " + max2 +"\n" );
		  
		  double[] density = new double[ coins.length ];
		  
		  for( int i=0; i<coins.length; i++ ) {
			  density[i] = coins[i].value/coins[i].weight;
		  }
		  /// Sort density 
		  Arrays.sort(density);
		  
		  /// Sort coins by density
		  for( int i=0; i<coins.length; i++ ){
			  for( int j=0; j<coins.length; j++ )
				  if( coins[j].value/coins[j].weight == density[i] ) {
					  Coin temp = coins[coins.length-i-1];
					  coins[coins.length-i-1] = coins[j];
					  coins[j] = temp;
					  break;
				  }
			  System.out.print( "coins[" + i + "] : (" + coins[i].weight + ", " + coins[i].value + "); \n");
		  }
		  
		  int max = 0;
		  /// Starting take the most density
		  ///for( int i=coins.length-1; i>=0; i-- ){
		  for( int i=0; i<coins.length; i++ ){
			  for( ; capacity>0; ) {
				  if( capacity >= coins[i].weight ) {
					  max += coins[i].value;
					  capacity -= coins[i].weight;
					  System.out.print( "coins[" + i + "] : (" + coins[i].weight + ", " + coins[i].value + "); \n");
				  }
				  else {
					  break;
				  }
			  }
		  }
		  		  
		  return max;
	}

  public static class Coin {
    int weight;
    int value;

    public Coin( int weight, int value) {
      this.weight = weight;
      this.value = value;
    }
  }
	
//  public static int solution( Cake[] cakes,  int capacity) {
//    int[] maxValueAtCapacity = new int[capacity + 1];
//
//    for (int i = 0; i <= capacity; i++) {
//      int currentMaxValue = 0;
//
//      for (int j = 0; j < cakes.length; j++) {
//         Cake cake = cakes[j];
//        if (cake.weight <= i) {
//          // should we use the cake or not?
//          // if we use the cake, the most kilograms we can include in addition to the cake
//          // we're adding is the current capacity minus the cake's weight. we find the max
//          // value at that integer capacity in our array max_values_at_capacities
//          int maxValueUsingCake = cake.worth + maxValueAtCapacity[i - cake.weight];
//
//          // now we see if it's worth taking the cake. how does the
//          // value with the cake compare to the current_max_value?
//          currentMaxValue = Math.max(maxValueUsingCake, currentMaxValue);
//        }
//      }
//
//      maxValueAtCapacity[i] = currentMaxValue;
//    }
//
//    return maxValueAtCapacity[capacity];
//  }
//
//  public static class Cake {
//    int weight;
//    int worth;
//
//    public Cake( int weight, int worth) {
//      this.weight = weight;
//      this.worth = worth;
//    }
//  }
  
	public static void main(String[] args) {
///		int[] A = {9,3,9,3,9,7,9};
		int[] A = { 2 };
		Coin[] coins = {new Coin(7, 160), new Coin(3, 90), new Coin(2, 15)};
		///Coin[] coins = {new Coin(7, 160), new Coin(18, 9990), new Coin(2, 15)};
		
		int max = max( coins, 20 );
		///int X=10, Y=85, D=30;
		///int N = solution( X, Y, D );
		
      System.out.print("Max = " + max );
	}

}

//import java.util.Arrays;
//
//public class test {
//	
//    public static int solution(int[] A) {
//        // write your code in Java SE 8
//        if( A.length == 1 )
//        	if( A[0] == 1 )
//        		return 2;
//        	else
//        		return 1;
//
//        Arrays.sort(A);
//
//        int min = 0;
//        for( int i=0; i<A.length; i++ ) {
//        	if( A[i] <=0 )
//        		continue;
//        	
//        	else if( (A[i] - min) > 1 ) {
//        			return min + 1;
//	        } else
//        		min = A[i];
//        }
//        return min + 1;
//    }
//
// //   public static int solution(int X, int Y, int D) {
//        // write your code in Java SE 8
//    	
////    	if( X >= Y )
////    		return 0;
////    	if( D >= (Y-X) )
////    		return 1;
////    	
////    	int s = ( Y-X ) / D;
////    	int r = ( Y-X )  %  D;
////    	if( r > 0 )
////    		s +=1;
////    	
////    	return s;
////    }
//
////    public static int solution(int[] A) {
////        // write your code in Java SE 8
////    if( A.length == 1 )
////    	return A[0];
////    
////       Arrays.sort(A); 
////       
////       for( int i=1; i<A.length; i+=2 ) {
////    	   if( A[i] != A[i-1] )
////    		   return A[i-1]; 
////       }
////       return A[A.length-1];
////        
////    }
//	
////    public static int solution(int N) {
////        // write your code in Java SE 8
////        String n = Integer.toBinaryString(N);
////        char[] ca = n.toCharArray();
////        
////        int max = 0;
////        int count = 0;        
////        for ( int i=0; i<ca.length; i++ ){
////            if( ca[i] == '0' )
////                count++;
////            else{
////                if( count > max )
////                    max = count;
////                count = 0;
////            }
////        }
////        return max;
////    }
//
//	public static void main(String[] args) {
/////		int[] A = {9,3,9,3,9,7,9};
//		int[] A = { 2 };
//		int N = solution( A );
//		///int X=10, Y=85, D=30;
//		///int N = solution( X, Y, D );
//		
//        System.out.print("N = " + N );
//	}
//	
//
//    
//
//}