A thief is robbing a museum and he only has a single knapsack to carry all the items he steals.
The knapsack has a capacity for the amount of weight it can hold. Each item in the museum has a weight and a value associated with it.
Given the knapsack capacity and the weight and values of the items in the museum, find the maximum value the thief can steal. (Problem on HackerRank.)
Naive Solution: Try All Possible Ways Of Taking Items
The naive solution involves keeping track of the current value and weight of the knapsack, going through each item, and trying both ways of handling the item: we either leave it behind, or pick it up (if we have enough capacity left to hold its weight).
We can code this solution with a simple recursive function. Here's the C++ code for handling the naive knapsack solution:
The time complexity is O(2^numItems) because every recursive loop has two choices.
The space complexity is O(numItems) because each recursive loop travels down to each item and so the stack space goes that high.
Dynamic Programming (Best) Solution: Calculate Best Values Possible per Valid Knapsack Weights
The dynamic programming solution, like most DP solution, involves storing the best possible answer while going through each valid solution.
In the case of the knapsack problem, the DP solution is to generate a DP table that stores the maximum value a thief can steal at each item for each valid knapsack weight.
We build this table up by going through each item/knapsackWeight combination and taking the max of the choice "take this item, or don't" and choosing the highest value.
The dynamic programming C++ code that shows how to solve the knapsack problem is as follows:
The time complexity is O(numItems*knapsackCapacity) because that's the size of the DP table.
The space complexity is O(numItems*knapsackCapacity) because that's the size of the DP table.
Hi, I'm srcmake. I play video games and develop software.
Pro-tip: Click the "DIRECTORY" button in the menu to find a list of blog posts.
License: All code and instructions are provided under the MIT License.