# Algorithm for fractional knapsack problem

In this article, we are going to learn about **fractional knapsack problem**. **Algorithm for fractional knapsack with its example** is also prescribed in this article.

Submitted by Abhishek Kataria, on August 02, 2018

## Knapsack problem

The **knapsack problem or rucksack problem** is a problem in combinative or integrative optimization. In this kind of problem, there are set of items are given with a weight and a value, determine the number of each item included in a collection so that the total weight is less than or equal to the given limit and the total value is as large as possible.

## Fractional Knapsack problem

In **fractional knapsack fractions** of an item can be taken rather than having to make a binary choice for each of them. In this objective function is mathematically represented by:

Max

Where, **Pi= profit and Xi = fraction**.

Where, **Wi = weight** of the corresponding and **Xi= fraction**.

In this, at last, the output should be an array of the fraction item that we have taken, and in this, we also have to take output that gives the maximum profit.

### Algorithm for fractional knapsack

1. W and item have value V_{i}and weight W_{i}. 2. Rank item by value/weight ratio: V_{i}/W_{i}. 3. Thus : V_{i}/W_{i}= V_{j}/W_{j}for all i<=W_{j}. 4. Consider items in order of descending ratio. 5. Take as much of each item is possible. 6. Assume value and weight arrays are sorted by Vi<=Wi fractional knapsack (V,w,W) 7. Load:=0 8. i:=1 9. while load<w and i<=n loop 10. if 11. wi <=W –loop then 12. take all of item i 13. else 14. take (W-load)/wi of item i 15. end if 16. Add weight of what was taken to load. 17. i:i+1 18. end loop 19. return loop

**Example of fractional knapsack for the following instance by using greedy approach in which maximum value, M =25kg.**

S.no | Weight | Profit |
---|---|---|

1 | 10 | 30 |

2 | 5 | 20 |

3 | 15 | 40 |

4 | 8 | 36 |

**P=**

30 | 20 | 40 | 36 |

**W=**

10 | 5 | 15 | 8 |

**Now we will calculate the profit per unit capacity of knapsack: P/W**

3 | 4 | 2.6 | 4.5 |

**Now the fraction i.e. X**

1 | 1 | 2/15 | 1 |

**i.e. to calculate a total profit:**

P = P1X1 + P2X2 + P3X3 + P4X4 = 30×1+20×1+40×2/15+36×1 = 91.33

Related Tutorials

- Introduction to Algorithms
- Introduction to Greedy Strategy in Algorithms
- Stability in sorting
- External Merge Sorting Algorithm
- Radix Sort and its Algorithm
- Bucket Sort Algorithm
- Bubble sort Algorithm, Flow Chart and C++ Code
- Insertion sort Algorithm, flowchart and C, C++ Code
- Merge Sort | One of the best sorting algorithms used for large inputs
- Binary Search in C, C++
- Randomized Binary Search
- Meta Binary Search | One-sided Binary Search
- Difference between Linear Search and Binary Search
- Binary Search in String
- Variants of Binary Search
- Sieve of Eratosthenes to find prime numbers
- Optimal Merge Pattern (Algorithm and Example)
- Given an array of n numbers, Check whether there is any duplicate or not
- Finding the missing number
- Find the number occurring an odd number of times
- Find the pair whose sum is closest to zero in minimum time complexity
- Find three elements in an array such that their sum is equal to given element K
- Bitonic Search Algorithm
- Check whether a number is Fibonacci or not
- Segregate even and odd numbers in minimum time complexity
- Find trailing zeros in factorial of a number
- Find Nearest Greatest Neighbours of each element in an array
- Interpolation search algorithm
- Floor and ceil of an element in an array using C++
- Two Elements whose sum is closest to zero
- Find a pair with a given difference
- Count number of occurrences (or frequency) in a sorted array
- Find a Fixed Point (Value equal to index) in a given array
- Find the maximum element in an array which is first increasing and then decreasing
- Dynamic Programming (Components, Applications and Elements)
- Algorithm and procedure to solve a longest common subsequence problem
- Dynamic Programming (Components, Applications and Elements)
- Find the Nth Fibonacci number | C++
- Longest Common Subsequence using Dynamic programming (DP)
- Longest Increasing Subsequence using Dynamic programming (DP)
- Find the maximum sub-array sum using KADANE'S ALGORITHM
- Non-intersecting chords using Dynamic Programming (DP)
- Edit Distance using Dynamic Programming (DP)
- Finding Ugly Number using Dynamic Programming (DP)
- Egg dropping problem using Dynamic Programming (DP)
- Wild card matching problem using Dynamic programming (DP)
- Compute sum of digits in all numbers from 1 to N for a given N
- Minimum jumps required using Dynamic programming (DP)
- Graph coloring problem's solution using backtracking algorithm
- Breadth First Search (BFS) and Depth First Search (DFS) Algorithms
- Travelling Salesman Problem
- Kruskal's (P) and Prim's (K) Algorithms
- Multistage graph problem with forward approach and backward approach algorithms
- Floyd Warshall algorithm with its Pseudo Code

- Backtracking (Types and Algorithms)
- 4 Queen's problem and solution using backtracking algorithm
- N Queen's problem and solution using backtracking algorithm
- Find the GCD (Greatest Common Divisor) of two numbers using EUCLID'S ALGORITHM
- Compute the value of A raise to the power B using Fast Exponentiation
- Implement First Come First Served (FCFS) CPU Scheduling Algorithm using C program
- Implementations of FCFS scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Non-Preemptive CPU scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Preemptive CPU scheduling algorithm using C++
- Implementation of Priority scheduling (Pre-emptive) algorithm using C++
- Implementation of Priority scheduling (Non Pre-emptive) algorithm using C++
- Implementation of Round Robin CPU Scheduling algorithm using C++
- Analysis of LRU page replacement algorithm and Belady's anomaly
- Branch and Bound
- Find the roots of a complex polynomial equation using Regula Falsi Method in C
- Sieve of Eratosthenes to find prime numbers
- Implementations of FCFS scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Non-Preemptive CPU scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Preemptive CPU scheduling algorithm using C++
- Implementation of Priority scheduling (Pre-emptive) algorithm using C++
- Divide and Conquer Paradigm (What it is, Its Applications, Pros and Cons)
- Implementation of Priority scheduling (Non Pre-emptive) algorithm using C++
- Implementation of Round Robin CPU Scheduling algorithm using C++
- Jump Search Implementation using C++
- Optimal Merge Pattern (Algorithm and Example)
- Introduction to Greedy Strategy in Algorithms
- Strassen's Matrix Multiplication in algorithms
- Huffman Coding (Algorithm, Example and Time complexity)
- Backtracking (Types and Algorithms)
- 4 Queen's problem and solution using backtracking algorithm
- N Queen's problem and solution using backtracking algorithm
- Graph coloring problem's solution using backtracking algorithm
- Tournament Tree and their properties
- Deterministic and Non Deterministic Algorithms
- Lower Bound Theory
- Non Recursive Tree Traversal Algorithm
- Line Drawing Algorithm
- Breadth First Search (BFS) and Depth First Search (DFS) Algorithms
- P and NP problems and solutions | Algorithms
- Travelling Salesman Problem
- 2 – 3 Trees Algorithm
- Kruskal's (P) and Prim's (K) Algorithms
- Algorithm for fractional knapsack problem
- Algorithm and procedure to solve a longest common subsequence problem
- Midpoint Circle Algorithm
- Multistage graph problem with forward approach and backward approach algorithms
- Floyd Warshall algorithm with its Pseudo Code
- Reliability design problem
- Removing consecutive duplicates from a string
- Fast Exponentiation using Bitmasking

Comments and Discussions!