Collect Jewels Editorial

Practice Problem Link: Practice Problem | Collect Jewels

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

You discover a treasure containing n pieces of jewel stones. You have a sack to collect them but it can hold only contents upto weight capacity. You are given the weight and value of each of the stones - weight_i and value_i. Find the maximum value of stones that you can carry in the sack.

Naive Approach

We can solve this problem by using brute force recursion. Observe that for each object we have only 2 choices, either take the current object in the sack or leave it. We can recurse over all the possible choices, and take the optimal answer.

Analysis

• Time Complexity: O(2ⁿ)
• Space Complexity: O(1)

Implementation

C++

/* This is the JewelStone class definition
class JewelStone {
public:
   int weight, value;
   JewelStone(int weight, int value) {
       this->weight = weight;
       this->value = value;
   }
};
*/
int knapSack(vector<JewelStone*> &stones, int capacity, int n) {
   if(n == 0 || capacity == 0) {
       return 0;
   }
   if(stones[n - 1]->weight > capacity) {
       return knapSack(stones, capacity, n - 1);
   }
   return max(stones[n - 1]->value + knapSack(stones, capacity - stones[n - 1]->weight, n - 1), knapSack(stones, capacity, n - 1));
}
int getMaxValue(vector<JewelStone*> stones, int capacity) {
   return knapSack(stones, capacity, stones.size());
}

Java

class Solution {
   int knapSack(JewelStone[] stones, int capacity, int n) {
       if(n == 0 || capacity == 0) {
           return 0;
       }
       if(stones[n - 1].weight > capacity) {
           return knapSack(stones, capacity, n - 1);
       }
       return Math.max(stones[n - 1].value + knapSack(stones, capacity - stones[n - 1].weight, n - 1), knapSack(stones, capacity, n - 1));
     }
   int getMaxValue (JewelStone[] stones, int capacity) {
       return knapSack(stones, capacity, stones.length);
   }
}

Optimal Approach

We observe that several functions call in the knapSack() function are being repeated and recalculated again and again. So we can memoize the results of those function calls, and prevent them from being recalculated by using Dynamic Programming. We can have DP array which stores the optimal answer when we have to attain weight j by using first i elements in the array. This is a well-known DP problem called the Knapsack Problem.

Analysis

• Time Complexity: O(n * capacity)
• Space Complexity: O(n * capacity)

Implementation

C++

/* This is the JewelStone class definition
class JewelStone {
public:
   int weight, value;
   JewelStone(int weight, int value) {
       this->weight = weight;
       this->value = value;
   }
};
*/
vector<vector<int>> dp;
int knapSack(vector<JewelStone*> &stones, int capacity, int n) {
   if(n == 0 || capacity == 0) {
       return 0;
   }
   if(dp[n][capacity] != -1) {
       return dp[n][capacity];
   }
   if(stones[n - 1]->weight > capacity) {
       return dp[n][capacity] = knapSack(stones, capacity, n - 1);
   }
   return dp[n][capacity] = max(stones[n - 1]->value + knapSack(stones, capacity - stones[n - 1]->weight, n - 1), knapSack(stones, capacity, n - 1));
}
int getMaxValue(vector<JewelStone*> stones, int capacity) {
   vector<vector<int>> temp(stones.size() + 1, vector<int> (capacity + 1, -1));
   dp = temp;
   return knapSack(stones, capacity, stones.size());
}

Java

class Solution {
   int dp[][];
   int knapSack(JewelStone[] stones, int capacity, int n) {
       if(n == 0 || capacity == 0) {
           return 0;
       }
       if(dp[n][capacity] != -1) {
           return dp[n][capacity];
       }
       if(stones[n - 1].weight > capacity) {
           return dp[n][capacity] = knapSack(stones, capacity, n - 1);
       }
       return dp[n][capacity] = Math.max(stones[n - 1].value + knapSack(stones, capacity - stones[n - 1].weight, n - 1), knapSack(stones, capacity, n - 1));
     }
   int getMaxValue (JewelStone[] stones, int capacity) {
       dp = new int[stones.length + 1][capacity + 1];
       for(int i = 0; i <= stones.length; i++) {
           Arrays.fill(dp[i], -1);
       }
       return knapSack(stones, capacity, stones.length);
   }
}

Bottom-Up Implementation

C++

/* This is the JewelStone class definition
class JewelStone {
public:
   int weight, value;
   JewelStone(int weight, int value) {
       this->weight = weight;
       this->value = value;
   }
};
*/
int getMaxValue(vector<JewelStone*> stones, int capacity) {
   int dp[stones.size() + 1][capacity + 1];
   for(int i = 0; i <= stones.size(); i++) {
       for(int j = 0; j <= capacity; j++) {
           if(i == 0 || j == 0) {
               dp[i][j] = 0;
           } else if(j - stones[i - 1]->weight >= 0) {
               dp[i][j] = max(dp[i - 1][j - stones[i - 1]->weight] + stones[i - 1]->value, dp[i - 1][j]);
           } else {
               dp[i][j] = dp[i - 1][j];
           }
       }
   }
   return dp[stones.size()][capacity];
}

Java

class Solution {
   int getMaxValue (JewelStone[] stones, int capacity) {
       int[][] dp = new int[stones.length + 1][capacity + 1];
       for(int i = 0; i <= stones.length; i++) {
           for(int j = 0; j <= capacity; j++) {
               if(i == 0 || j == 0) {
                   dp[i][j] = 0;
               } else if(j - stones[i - 1].weight >= 0) {
                   dp[i][j] = Math.max(dp[i - 1][j - stones[i - 1].weight] + stones[i - 1].value, dp[i - 1][j]);
               } else {
                   dp[i][j] = dp[i - 1][j];
               }
           }
       }
       return dp[stones.length][capacity];
   }
}