CareerCup

Greedy / Knapsack 0/1 ?

Its a knapsack problem where we have to minimize value instead of maximizing it.

0-1 knapsack problem - If it is mandatory to pick all books of given price.

Fractional knapsack problem - If it is allowed to pick any quantity of books of given price.

This is very good point to discuss with your interviewer.

Simplex method....

I suppose, dynamic programming can help to solve this in O(n^2).
Code below:

public static int optimalPrice(int amount) {
        if (amount == 0) return 0;

        if (cache.containsKey(amount)) return cache.get(amount);

        int result = 100000;
        for (int i = 0; i < quantities.length; i++) {
            int q = quantities[i];
            int p = prices[i];

            if (amount >= q) {
                int t = optimalPrice(amount - q) + p;
                if (t < result) result = t;
            }
        }

        cache.put(amount, result);
        return result;
    }

public class PurchaseQBooksWithMinPrice {

public static void main(String[] args){
int arr[]= {100,200,120,130,165};
int quanity[] = {10,20,30,15,25};
for(int i = 0; i < arr.length; i++){
System.out.println(arr[i]+" "+quanity[i]);
}
System.out.println();

quickSort(arr,quanity, arr.length);
for(int i = 0; i < arr.length; i++){
System.out.println(arr[i]+" "+quanity[i]);
}

System.out.println(getPrice(arr,quanity,50));
}

private static int getPrice(int[] arr, int[] quanity,int totalQ) {
int tq=0;
int price = 0;
for(int i = 0; i<arr.length;i++){
if(tq == totalQ){
return price;
}
if(tq + quanity[i] < totalQ){
price += arr[i]*quanity[i];
tq = tq + quanity[i];
}else if(tq + quanity[i] > totalQ){
price += (totalQ-tq)*arr[i];
tq = totalQ;
}
}
if(tq == totalQ){
return price;
}else{
return -1; //Incase the total quantity is less than quantity given as input
}
}

private static void quickSort(int[] arr, int[] quantity, int length) {
recQuickSort(arr,quantity, 0, length - 1);
}

private static void recQuickSort(int[] arr,int []quantity, int left, int right) {
if(right - left <= 0)
return;
else{
int pivot = arr[right];
int partition = partitionIt(arr,quantity,left, right, pivot);
recQuickSort(arr,quantity, left, partition-1);
recQuickSort(arr,quantity, partition+1, right);
}

}

private static int partitionIt(int[] arr,int[] quantity, int left, int right, int pivot) {
int leftPtr = left - 1;
int rightPtr = right;
int temp;
while(true){
while(arr[++leftPtr]<pivot);
while(rightPtr > 0 && arr[--rightPtr]>pivot);
if(leftPtr >= rightPtr)
break;
else{
temp = arr[leftPtr];
arr[leftPtr]= arr[rightPtr];
arr[rightPtr]= temp;

temp = quantity[leftPtr];
quantity[leftPtr]= quantity[rightPtr];
quantity[rightPtr]= temp;
}
}
temp = arr[leftPtr];
arr[leftPtr]= arr[right];
arr[right] = temp;

temp = quantity[leftPtr];
quantity[leftPtr]= quantity[right];
quantity[right] = temp;
return leftPtr;

}

}

public class BuyBooks {
    
    int[] bundle={10, 20, 30, 15, 25};
    int[] price ={100, 200, 120, 130, 165};
    BookOffer[] offers;
    
    public BuyBooks() {
        super();
    }

    private  void loadValues() {
        offers=new BookOffer[bundle.length];
        for(int i=0;i<bundle.length;i++){
          offers[i]=new BookOffer(bundle[i], price[i]);
        }
       qsort();
    }

    private void qsort(){
     
      quicksort(0,offers.length-1);
     
    }

    private BookOffer[] quicksort( int low,int high) {
    
   
//    System.out.println("Quick sorting"+low +" "+high);  
    int i = low, j = high;
    // Get the pivot element from the middle of the list
    BookOffer pivot = offers[low + (high-low)/2];

    // Divide into two lists
    while (i <= j) {
      // If the current value from the left list is smaller then the pivot
      // element then get the next element from the left list
      while (offers[i].costfactor < pivot.costfactor) {
        i++;
      }
      // If the current value from the right list is larger then the pivot
      // element then get the next element from the right list
      while (offers[j].costfactor > pivot.costfactor) {
        j--;
      }

      // If we have found a values in the left list which is larger then
      // the pivot element and if we have found a value in the right list
      // which is smaller then the pivot element then we exchange the
      // values.
      // As we are done we can increase i and j
      if (i <= j) {
        exchange(i, j);
        i++;
        j--;
      }
    }
    // Recursion
    if (low < j)
      quicksort(low, j);
    if (i < high)
      quicksort(i, high);
    
    return offers;
  }

  private void exchange(int i, int j) {
    BookOffer temp = offers[i];
    offers[i] = offers[j];
    offers[j] = temp;
  } 
    


    public static void main(String[] args) {
        BuyBooks buyBooks = new BuyBooks();
        buyBooks.loadValues();
        for(BookOffer b: buyBooks.offers){
//        System.out.println(b);
        }
        
        buyBooks.bestBuy(100);
        
    }

    private  void bestBuy(int cnt) {
        int fchoice,schoice,thirdchoice;
        int div;
        for(int i=0;i<this.offers.length;i++){
          System.out.println(this.offers[i]);
            if((div=cnt/offers[i].bundle)>=1){
              System.out.println("Buy"+(div*offers[i].bundle)+"@"+(div*offers[i].price));
              cnt-=div*offers[i].bundle;
            }
        }
        
    }
}

    class BookOffer{
       int bundle;
       int price;
       double costfactor;
       
       BookOffer(int bundle,int price){
         this.bundle=bundle;
         this.price=price;
         this.costfactor=price/bundle;
       }
       
       public String toString(){
         return this.bundle+"books of bundle costs"+this.price+" at cost"+this.costfactor;
       }
       
    }

short by price
the use divide and concur to find @t what point quantity limit is reached or more

This is very similar to the rod-cutting example provided in Introduction to algorithms CLRS book under section dynamic programming isn't it?

If i got the question right:-
"user wants to purchase 500 quantity of books.come up with minimum price"

if user want 500 quantity of books, with minimun prices, so not get the 500 copies of book which has minimum price.

or may be i got the question wrong...

HashTable<P,Q> hashtable; //Store all the Price and Quantity in hash

HashSet set = hashtable.getKeys();
hashSet sortedSet = Collection.Sort(set);

iterator i = sortedSet.iterator();

int total_p =0. total_q=0;
While(i.hasNext())
{
int p=i.next();
int q= hastable.getValue(p);
if(target-total_q <=q){
total_q+=q;
total_p+=p*q;
}
else{
int rem = target-total_q;
total_q+=rem;
total_p+=rem*p;
return total_p;
}
}

return -1;

#include<stdio.h>
int max(int a, int b) { return (a > b)? a : b; }
int knapSack(int W, int wt[], int val[], int n)
{
if (n == 0 || W == 0)
return 0;

if (wt[n-1] > W)
return knapSack(W, wt, val, n-1);

// Return the maximum of two cases: (1) nth item included (2) not included
else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
knapSack(W, wt, val, n-1)
);
}

// Driver program to test above function
int main()
{
int val[] = {60, 100, 120};
int wt[] = {10, 20, 30};
int W = 50;
int n = sizeof(val)/sizeof(val[0]);
printf("%d", knapSack(W, wt, val, n));
return 0;
}

Dynamic Programming based implementation.

#include<stdio.h>
 
// A utility function that returns maximum of two integers
int max(int a, int b) { return (a > b)? a : b; }
 
// Returns the maximum value that can be put in a knapsack of capacity W
int knapSack(int W, int wt[], int val[], int n)
{
   int i, w;
   int K[n+1][W+1];
 
   // Build table K[][] in bottom up manner
   for (i = 0; i <= n; i++)
   {
       for (w = 0; w <= W; w++)
       {
           if (i==0 || w==0)
               K[i][w] = 0;
           else if (wt[i-1] <= w)
                 K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]);
           else
                 K[i][w] = K[i-1][w];
       }
   }
 
   return K[n][W];
}
 
int main()
{
    int val[] = {60, 100, 120};
    int wt[] = {10, 20, 30};
    int  W = 50;
    int n = sizeof(val)/sizeof(val[0]);
    printf("%d", knapSack(W, wt, val, n));
    return 0;
}

Recursion, test it simply copy and paste this in your console!

function knapack(require_amount){

	var a = {
		quantity: 10,
		price: 100
	}

	var b = {
		quantity: 20,
		price: 200
	}

	var c = {
		quantity: 30,
		price: 120
	}

	var d = {
		quantity:15,
		price: 130
	}

	var e = {
		quantity: 25,
		price: 165
	}

	var arr = [a,b,c,d,e];

	return min_price(arr, require_amount, 0);
}

function min_price(arr, require_amount, price){
	if(require_amount === 0) return price;
	if(require_amount < 0) return Infinity;

	var result_arr = [];
	for(var i = 0; i < arr.length; i++){
		var item = min_price(arr, require_amount - arr[i].quantity, price + arr[i].price);
		result_arr.push(item);
	}

	return Math.min.apply(null, result_arr);
}


knapack(100);

1 calculate the avg price of per quality for each books
2 choose the lowest one and pick as many as we can
3 do the same procedure if any quality left

i guess that would get the job done

what if we sort books by prices, and take all available books from chipper to expensive until we reach the quantity. Complexity is O(N log N)