Challenge 1: The 0/1 Knapsack Problem

Welcome to your first dynamic programming problem! Remember to work your way up to the correct solution. It might help to think of the brute force solution first, then memoize it or tabulate it. The process of coming up with a solution to a problem like this would be similar in a real interview. Remember, you can discuss it with your interviewer and talk out loud while you’re implementing the solution. Good luck!

P.S changing the prototype of the given function would result in an error. If the need to change it arises, create another function and call it from the one that is given.

Problem Statement

We’ve already covered the fractional knaspack problem in the greedy algorithms chapter. Let’s now look at the 0/1 knapsack problem. Imagine that you’re a burglar at a jewelry store with a knapsack. Your goal is to choose a combination of jewelry that results in the most profit. Let’s see how you would code this problem.

Given two integer arrays that represent the weights and profits of N items, implement a function knapSack() that finds a subset of these items which will give us the maximum profit so that their cumulative weight is not more than a given number capacity. Each item can only be selected once, which means we either skip it or put it in the knapsack.