Session 2

The fractional knapsack problem is a variation of the classic knapsack problem where you are allowed to take fractions of items rather than having to take whole items. The goal is to maximize the total value of the items you can carry in a knapsack with a given weight capacity. It's a greedy algorithm problem that can be solved efficiently by following a specific approach.

Solution Approach

1. Calculate Value-to-Weight Ratio: For each item, calculate the value-to-weight ratio, which is the value of the item divided by its weight. This ratio helps to determine which items are more valuable per unit of weight.

2. Sort Items: Sort the items in descending order based on their value-to-weight ratio. This ensures that you consider the most valuable items first.

3. Initialize Variables: Initialize a variable to keep track of the total value and the remaining weight capacity of the knapsack.

4. Iterate Through Sorted Items: Iterate through the sorted list of items. For each item, check if it can fit in the remaining weight capacity of the knapsack.

   • If the item can fit completely, add its full value to the total value and decrease the remaining weight capacity accordingly.
   • If the item cannot fit completely, take the fraction of the item that can fit in the remaining weight capacity, add the corresponding fraction of the value to the total value, and set the remaining weight capacity to zero (since the knapsack is now full).

5. Return Total Value: After iterating through all the items, return the total value of the items in the knapsack.

Example

Suppose you have the following items with their weights and values:

And the knapsack has a weight capacity of 50. The value-to-weight ratios for the items are:

• Item 1: 60/10 = 6
• Item 2: 100/20 = 5
• Item 3: 120/30 = 4 Sorting the items by their value-to-weight ratio gives us:

1. Item 1 (6)
2. Item 2 (5)
3. Item 3 (4) Now, we can start filling the knapsack:

• Item 1 can fit completely (weight 10), so we add its full value (60) to the total value and reduce the remaining capacity to 40.
• Item 2 can also fit completely (weight 20), so we add its full value (100) to the total value and reduce the remaining capacity to 20.
• Item 3 cannot fit completely (weight 30), but we can take a fraction of it. We can take 20/30 of item 3, which gives us a value of (20/30) * 120 = 80. We add this to the total value and reduce the remaining capacity to 0. The total value in the knapsack is 60 (from item 1) + 100 (from item 2) + 80 (from item 3) = 240. Therefore, the maximum value that can be obtained with the given weight capacity is 240.

Time Complexity

The time complexity of the fractional knapsack problem is O(n log n) due to the sorting step, where n is the number of items. The rest of the operations (calculating ratios and iterating through the items) take O(n) time.

Objectives

The main objectives of this session are to:

• Implement Fractional Knapsack Problem
• Test the implementation on different problem instances
• Implement greedy technique in general

Problem Statement

Implement Fractional Knapsack Algorithm and find out optimal result for the following problem instances:

Question 1

(P1, P2, P3, P4, P5, P6, P7) = (15, 5, 20, 8, 7, 20, 6)
(W1, W2, W3, W4, W5, W6, W7) = (3, 4, 6, 8, 2, 2, 3)
Maximum Knapsack Capacity = 18

Question 2

(P1, P2, P3, P4, P5) = (20, 30, 40, 32, 55)
(W1, W2, W3, W4, W5) = (5, 8, 10, 12, 15)
Maximum Knapsack Capacity = 20

Question 3

(P1, P2, P3, P4, P5, P6, P7) = (12, 10, 8, 11, 14, 7, 9)
(W1, W2, W3, W4, W5, W6, W7) = (4, 6, 5, 7, 3, 1, 6)
Maximum Knapsack Capacity = 15

Implementation

Python

		# Fractional Knapsack in Python
def get_max_value(profits, weights, capacity):
    # Calculate profit/weight ratio and keep track of original index
    items = []
    for i in range(len(profits)):
        items.append(
            {
                "id": i + 1,
                "profit": profits[i],
                "weight": weights[i],
                "ratio": profits[i] / weights[i],
            }
        )
 
    # Sort items by ratio in descending order (Greedy Strategy)
    items.sort(key=lambda x: x["ratio"], reverse=True)
 
    total_value = 0.0
    for item in items:
        if capacity > 0 and capacity >= item["weight"]:
            # Take the full item
            capacity -= item["weight"]
            total_value += item["profit"]
        elif capacity > 0:
            # Take a fraction of the item to fill remaining capacity
            total_value += item["profit"] * (capacity / item["weight"])
            capacity = 0
            break
 
    return total_value
 
 
# Solving Question 1
p1, w1, c1 = [15, 5, 20, 8, 7, 20, 6], [3, 4, 6, 8, 2, 2, 3], 18
print(f"Result Q1: {get_max_value(p1, w1, c1):.2f}")
	

C Language

		#include <stdio.h>
#include <stdlib.h>
 
typedef struct {
    int id;
    double p, w, ratio;
} Item;
 
// Comparator for descending order based on ratio
int compareItems(const void* a, const void* b) {
    Item* itemA = (Item*)a;
    Item* itemB = (Item*)b;
    if (itemB->ratio > itemA->ratio) return 1;
    if (itemB->ratio < itemA->ratio) return -1;
    return 0;
}
 
double fractionalKnapsack(double p[], double w[], int n, double capacity) {
    Item items[n];
    for (int i = 0; i < n; i++) {
        items[i].id = i + 1;
        items[i].p = p[i];
        items[i].w = w[i];
        items[i].ratio = p[i] / w[i];
    }
 
    qsort(items, n, sizeof(Item), compareItems);
 
    double totalProfit = 0.0;
    for (int i = 0; i < n; i++) {
        if (capacity >= items[i].w) {
            capacity -= items[i].w;
            totalProfit += items[i].p;
        } else {
            // Add the fractional part
            totalProfit += items[i].p * (capacity / items[i].w);
            break;
        }
    }
    return totalProfit;
}
 
int main() {
    double p2[] = {20, 30, 40, 32, 55};
    double w2[] = {5, 8, 10, 12, 15};
    printf("Result Q2: %.2f\n", fractionalKnapsack(p2, w2, 5, 50));
    return 0;
}
	

Rust

		#[derive(Debug)]
struct Item {
    p: f64,
    w: f64,
    ratio: f64,
}
 
fn solve_knapsack(profits: &[f64], weights: &[f64], mut capacity: f64) -> f64 {
    let mut items: Vec<Item> = profits
        .iter()
        .zip(weights.iter())
        .map(|(&p, &w)| Item { p, w, ratio: p / w })
        .collect();
 
    // Sort by ratio descending
    // partial_cmp is used because f64 doesn't implement total ordering
    items.sort_by(|a, b| b.ratio.partial_cmp(&a.ratio).unwrap());
 
    let mut total_profit = 0.0;
 
    for item in items {
        if capacity <= 0.0 {
            break;
        }
 
        if item.w <= capacity {
            capacity -= item.w;
            total_profit += item.p;
        } else {
            // Take fraction
            total_profit += item.p * (capacity / item.w);
            capacity = 0.0;
        }
    }
    total_profit
}
 
fn main() {
    let p3 = vec![12.0, 10.0, 8.0, 11.0, 14.0, 7.0, 9.0];
    let w3 = vec![4.0, 6.0, 5.0, 7.0, 3.0, 1.0, 6.0];
    let capacity = 15.0;
 
    println!("Result Q3: {:.2}", solve_knapsack(&p3, &w3, capacity));
}
	

Conclusion

The fractional knapsack problem is a fundamental problem in combinatorial optimization that can be efficiently solved using a greedy algorithm. By calculating the value-to-weight ratio and sorting the items accordingly, we can maximize the total value of the items in the knapsack while respecting the weight capacity. This problem has practical applications in various fields such as resource allocation, budgeting, and logistics. Understanding the fractional knapsack problem and its solution approach is essential for solving more complex optimization problems in computer science and operations research.