Cake Thief

Problem

You are a cake thief, who wants to steal cakes from a shop. 

Each cake has a weight and a value, stored in tuples with two indices:

An integer representing the weight of the cake in kilograms

An integer representing the monetary value of the cake in British pounds

For example:

Cake #1 weighs 7 kilograms and has a value of 160 pounds i.e. (7, 160)

Cake #2 weighs 3 kilograms and has a value of 90 pounds i.e. (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 that takes an array of cake type tuples and weight capacity, and returns the cakes to steal to get maximum profit.

What if there are unlimited cakes of each type? i.e. you can steal many cakes of a given weight 7 and price 160 and so on.

Solution

//Cake.java
public class Cake { 
 int price;
 int weight;

 public Cake(int weight, int price) {
  this.price = price;
  this.weight = weight;
 }
}

//CakeThief.java
import java.util.ArrayList;
import java.util.Comparator;

public class CakeThief {


 public ArrayList steal(ArrayList cakeList, int maxWt)
 {
  //Part 1: Sort the cakes according to their weights
  cakeList.sort(new Comparator(){
   @Override
   public int compare(Cake c1, Cake c2) {
    return c1.weight - c2.weight;
   }
  });

  //Part 2: Computer max value for a given number of items in an array
  int[][] sack = new int[cakeList.size()+1][maxWt+1];
  for(int i= 0; i< cakeList.size()+1; i++)
  {
   for(int j= 0; j < maxWt+1; j++)
   {
    if(i==0 || j==0) sack[i][j] = 0;
    else 
    {
     int wt = cakeList.get(i-1).weight;
     if(wt <= j)
     {
      int price = cakeList.get(i-1).price;
      sack[i][j] = Math.max(price + sack[i-1][j-wt], sack[i-1][j]);

      // if duplicate cakes allowed, this line should be 

      // sack[i][j] = Math.max(price + sack[i][j-wt], sack[i-1][j]);

     }
     else sack[i][j] = sack[i-1][j];
    }
    System.out.print(sack[i][j]);
   }
   System.out.println();
  }

  //Part 3: see which cakes form the optimal solution
  ArrayList result = new ArrayList();
  int i = cakeList.size();
  int j = maxWt;
  while(i>= 1 && j>= 0)
  {
   if(sack[i][j] > sack[i-1][j])
   {
    result.add(cakeList.get(i-1));
    j = j - cakeList.get(i-1).weight;
   }
   i = i-1;

   //if duplicate cakes allowed, this line should be 

   //else  i = i-1;
  }
  return result;
 }

 public void printCakeArray(ArrayList stolen)
 {
  for(int i= 0; i < stolen.size(); i++)
  {
   System.out.println("(" +  stolen.get(i).weight 
     + ", " + stolen.get(i).price + ")");
  }
 }

 public static void main(String[] args) {
  ArrayList cakeList = new ArrayList();
  cakeList.add(new Cake(1,1));
  cakeList.add(new Cake(3,4));
  cakeList.add(new Cake(5,7));
  cakeList.add(new Cake(4,5));

  CakeThief thief = new CakeThief();
  ArrayList stolen = thief.steal(cakeList, 7);
  thief.printCakeArray(stolen);
 }
}

Reference: 

https://www.youtube.com/watch?v=8LusJS5-AGo