Greedy Knapsack Problem

Problem statement

You are given N items. Each of these items has two parameters: weight and cost. Let’s define M as the sum of the weights of all the items.

Your task is to determine the most expensive cost of a knapsack whose capacity equals 1, 2, …, M. The cost of a knapsack equals the sum of the costs of all the elements of the knapsack. When you have a knapsack with a capacity equal to C, you can fill it with items whose sum of weights is not greater than C.

Solution: Greedy approach

An efficient solution to this problem involves using the Greedy approach. The basic idea of the Greedy approach is to calculate the ratio $\frac{value}{weight}$ of each item and sort the item on the basis of this ratio. Then, take the item with the highest ratio and add them until we can’t add the next item as a whole, and at the end, add the next item as much as we can, which will always be the optimal solution to this problem.

Let us first look at an example to understand this approach. After that, we can move on to the implementation.

Let us take the weight of the knapsack, W = 50. We have been given the following inputs: