We will discuss the Fractional Knapsack Problem, pseudo code, Code implementation of Fractional Knapsack in C, Java, JavaScript, Python, advantages & disadvantages, and time complexity of Fractional Knapsack.

## Table of Contents

## 1. What is Fractional Knapsack Problem?

The **Fractional Knapsack Problem** is a classic optimization problem that can be solved using a greedy algorithm.

In the Fractional Knapsack problem, items are given along with their weight and profit. The target is to maximize the profit considering the weight constraint.

Unlike the 0/1 Knapsack problem, you can take fractions of items, meaning you can break the items into smaller pieces.

### 1.1 Solution by Greedy Algorithm

- In fractional knapsack, first of all, profit value/weight ratios are calculated and then sorted in descending order.
- An item with the highest value/weight ratio is chosen and added to the collection.
- The maximum weight is checked after adding each item.
- If the entire item cannot be included, then a fraction of it is added to the collection.

## 2. Pseudocode for Fractional Knapsack

Greedy-fractional-knapsack (w, v, W)1. for i =1 to n 2. Do x[i] =0 3. weight = 0 4. while weight < W 5. Do i = best remaining item 6. if ( weight + w[i] W) 7. Then x[i] = 1 8. weight = weight + w[i] 9. else 10. x[i] = (w - weight) / w[i] 11. weight = W 12. Return x

## 3. Code Implementation of Fractional Knapsack Problem

### 3.1 Fractional Knapsack in C

#include <stdio.h> // Structure for an item struct Item { int value; int weight; }; // Comparison function to sort items by value/weight ratio int compare(const void *a, const void *b) { double r1 = (double)((struct Item *)a)->value / ((struct Item *)a)->weight; double r2 = (double)((struct Item *)b)->value / ((struct Item *)b)->weight; return r2 - r1; } // Function to get maximum value double fractionalKnapsack(int W, struct Item arr[], int n) { qsort(arr, n, sizeof(struct Item), compare); double totalValue = 0.0; for (int i = 0; i < n; i++) { if (arr[i].weight <= W) { W -= arr[i].weight; totalValue += arr[i].value; } else { totalValue += arr[i].value * ((double) W / arr[i].weight); break; } } return totalValue; } int main() { int W = 50; struct Item arr[] = {{60, 10}, {100, 20}, {120, 30}}; int n = sizeof(arr) / sizeof(arr[0]); printf("Maximum value we can obtain = %f\n", fractionalKnapsack(W, arr, n)); return 0; }

#### 3.1.1 Explanation of Fractional Knapsack

**Class Item**: Defines*Item*with*value*and*weight*.**fractional_knapsack Function**:- Sorts items by value-to-weight ratio.
- Initializes
*total_value*. - Iterates through items, adding them to the knapsack.

**Example Usage**: Initializes*W*and*arr*. Calls*fractional_knapsack*and prints the result.

### 3.2 Fractional Knapsack in Java

import java.util.Arrays; import java.util.Comparator; class Item { int value, weight; Item(int value, int weight) { this.value = value; this.weight = weight; } } public class FractionalKnapsack { private static double getMaxValue(int W, Item[] arr) { Arrays.sort(arr, new Comparator<Item>() { public int compare(Item a, Item b) { double r1 = (double) a.value / a.weight; double r2 = (double) b.value / b.weight; return Double.compare(r2, r1); } }); double totalValue = 0.0; for (Item item : arr) { if (item.weight <= W) { W -= item.weight; totalValue += item.value; } else { totalValue += item.value * ((double) W / item.weight); break; } } return totalValue; } public static void main(String[] args) { int W = 50; Item[] arr = {new Item(60, 10), new Item(100, 20), new Item(120, 30)}; System.out.println("Maximum value we can obtain = " + getMaxValue(W, arr)); } }

### 3.3 Fractional Knapsack in JavaScript

class Item { constructor(value, weight) { this.value = value; this.weight = weight; } } function fractionalKnapsack(W, arr) { arr.sort((a, b) => (b.value / b.weight) - (a.value / a.weight)); let totalValue = 0; for (let item of arr) { if (item.weight <= W) { W -= item.weight; totalValue += item.value; } else { totalValue += item.value * (W / item.weight); break; } } return totalValue; } let W = 50; let arr = [new Item(60, 10), new Item(100, 20), new Item(120, 30)]; console.log("Maximum value we can obtain = " + fractionalKnapsack(W, arr));

### 3.4 Fractional Knapsack in Python

class Item: def __init__(self, value, weight): self.value = value self.weight = weight def fractional_knapsack(W, arr): arr.sort(key=lambda x: x.value / x.weight, reverse=True) total_value = 0 for item in arr: if item.weight <= W: W -= item.weight total_value += item.value else: total_value += item.value * (W / item.weight) break return total_value W = 50 arr = [Item(60, 10), Item(100, 20), Item(120, 30)] print("Maximum value we can obtain =", fractional_knapsack(W, arr))

## 4. Advantages of Fractional Knapsack

**Efficiency**: The greedy approach ensures that we get the optimal solution in a relatively simple and efficient manner.**Flexibility**: Allows for taking fractions of items, which can be practical in real-world scenarios.

## 5. Disadvantages of Fractional Knapsack

**Limited Scope**: Only applicable to problems where items can be divided. It doesn’t work for 0/1 Knapsack problems.**Sorting Overhead**: The need to sort items by their value-to-weight ratio adds to the complexity, making the algorithm O(n log n).

## 6. Time Complexity of Fractional Knapsack

If the ratio of *v _{i}/w_{i}* is already sorted in decreasing order, then the time taken by the while loop will be O(n). So, the

**total time required will be O(n log n).***FAQs*

*FAQs*

### What is Fractional Knapsack?

The **Fractional Knapsack Problem** is a classic optimization problem that can be solved using a greedy algorithm.

In the Fractional Knapsack problem, items are given along with their weight and profit. The target is to maximize the profit considering the weight constraint.

Unlike the 0/1 Knapsack problem, you can take fractions of items, meaning you can break the items into smaller pieces.

### What are the advantages of Fractional Knapsack?

**Efficiency**: The greedy approach ensures that we get the optimal solution in a relatively simple and efficient manner.**Flexibility**: Allows for taking fractions of items, which can be practical in real-world scenarios.

### What are the disadvantages of Fractional Knapsack?

**Limited Scope**: Only applicable to problems where items can be divided. It doesn’t work for 0/1 Knapsack problems.**Sorting Overhead**: The need to sort items by their value-to-weight ratio adds to the complexity, making the algorithm O(n log n).