Challenge: The 0/1 Knapsack Problem

In this challenge, we'll introduce the famous "knapsack problem" and solve a coding challenge on it.

We'll cover the following

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 to 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

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 that will gives us the maximum profit without their cumulative weight exceeding a given number capacity. Each item can only be selected once, which means we either skip it or put it in the knapsack.

Input

The input includes:

  1. The profit that can be gained by each piece of the jewelry
  2. The number of pieces of jewelry
  3. The weight of each piece of jewelry
  4. The maximum weight that the knapsack can hold
  5. The length of the array

Output

The maximum profit that can be returned

Sample input

    int profit[] = {60, 100, 120}; 
    int profitsLength;
    int weight[] = {10, 20, 30}; 
    int weightsLength;
    int capacity = 50;

Sample output

    220

Coding exercise

Take a close look and design a step-by-step algorithm before jumping to the implementation. This problem is designed for your practice, so try to solve it on your own first. If you get stuck, you can always refer to the hint and solution provided in the code tab. Good Luck!

class KnapsackProblem
{ 
    static int Knapsack(int profits[], int profitsLength, int weights[], int weightsLength, int capacity) 
    {
        // write your code here
        return -1;
    }
};