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}$ ...