Fractional Knapsack Problem – Programming Solution

Fractional Knapsack Problem Question:

You are required to implement the fractional knapsack problem using a programming language of your own choice. You are going to take the number of items, their weights, volume and costs 5 from the user as well as the knapsack capacity and determine the maximum value that can be 6 taken. Also, print out the items and its quantities that can be taken.

Background:

An efficient solution is to use Greedy approach. The basic idea of the greedy approach is to calculate the ratio value/weight for each item and sort the item on 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.

A simple code with our own comparison function can be written as follows, please see sort function more closely, the third argument to sort function is our comparison function which sorts the item according to value/weight ratio in non-decreasing order.
After sorting we need to loop over these items and add them in our knapsack satisfying above-mentioned criteria.

A greedy algorithm has five components:

1. A set of candidates, from which to create solutions.
2. A selection function, to select the best candidate to add to the solution.
3. A feasible function is used to decide if a candidate can be used to build a solution.
4. An objective function, fixing the value of a solution or an incomplete solution.
5. An evaluation function, indicating when you find a complete solution.

Solution:

Output:Execution of Fractional Knapsack Problem

View More samples: Here!

There are two critical components of greedy decisions:

1. Way of greedy selection. You can select which solution is best at present and then solve the subproblem arising from making the last selection. The selection of greedy algorithms may depend on previous selections. But it cannot depend on any future selection or depending on the solutions of subproblems. The algorithm evolves in a way that makes selections in a loop, at the same time shrinking the given problem to smaller subproblems.
2. Optimal substructure. You perform the optimal substructure for a problem if the optimal solution of this problem contains optimal solutions to its subproblems.

Github: implementation

Reference:

• https://www.guru99.com/fractional-knapsack-problem-greedy.html
• https://www.geeksforgeeks.org/fractional-knapsack-problem