Introduction

Given two integer arrays to represent weights and profits of ‘N’ items, find a subset of these items that will give us maximum profit such that their cumulative weight is not more than a given number ‘C’, and return the maxium profit. Each item can only be selected once, which means either we put an item in the knapsack or we skip it.

Let’s take Merry’s example, who wants to carry some fruits in the knapsack to get maximum profit. Here are the weights and profits of the fruits:

Items: { Apple, Orange, Banana, Melon }

Weights: { 2, 3, 1, 4 }