Fraction Knapsack problem

 Fractional Knapsack Problem (Simple Explanation Using Greedy Approach)

The Fractional Knapsack Problem is an optimization challenge where you're allowed to take portions of items to maximize the total value in a bag (knapsack) with a fixed weight limit. Each item has a specific value and weight, and instead of choosing whole items only, you can include a fraction of an item if it helps achieve a higher total value without exceeding the knapsack’s capacity. This problem is commonly solved using a greedy approach, where items are sorted based on their value-to-weight ratio, and the most valuable per unit weight items are selected first.

By picking the highest value-to-weight items and filling the bag either fully or partially with them, we ensure that every bit of space contributes maximally to the overall profit. For instance, if an item doesn’t completely fit into the remaining capacity, we simply include the fraction that does. This strategy guarantees an optimal solution for the fractional version of the problem, unlike the 0/1 knapsack, which requires more complex dynamic programming techniques.

Problem Definition:

You have a knapsack (bag) with a maximum weight capacity (W), and a list of items. Each item has:

• A weight (wᵢ)
• A value (vᵢ)

You can take fractions of items (unlike the 0/1 knapsack problem). Your goal is to maximize the total value in the knapsack without exceeding the weight limit (W). 

Here we consider weight as W and Profit as P

it is of three types

1.largest weight

2. smallest weight

3. largest profit weight ratio

all the types are solved below with examples one by one

---

Greedy Approach (Step-by-Step):

The greedy method works by making the best possible choice at each step without worrying about future consequences.

Type 1:  Largest profit-to-Weight Ratio 

Steps:

1. Calculate Value-to-Weight Ratio for each item:

Ratio=viwiRatio=wi​vi​​

(This tells us how much value we get per unit weight.)

2. Sort Items in Descending Order of this ratio (highest value per weight first).
3. Pick Items Greedily:
4. Take as much as possible of the item with the highest ratio.
• If the whole item cannot fit, take a fraction of it to fill the knapsack . Let's solve the fractional knapsack problem step-by-step. 
• Calculate  Largest Profit-to-Weight Ratios:
• 1.We need to calculate the profit-to-weight ratio (P/W) for each item.
• • Item 1: P/W = 18/7 ≈ 2.57
  • Item 2: P/W = 5/2 = 2.5
  • Item 3: P/W = 9/3 = 3
  • Item 4: P/W = 10/5 = 2
  • Item 5: P/W = 12/3 = 4
  • Item 6: P/W = 7/2 = 3.5

  2. Sort Items by Profit-to-Weight Ratio (Descending Order):

  We sort the items in descending order of their P/W ratios.

  • Item 5: P/W = 4, W = 3, P = 12
  • Item 6: P/W = 3.5, W = 2, P = 7
  • Item 3: P/W = 3, W = 3, P = 9
  • Item 1: P/W = 2.57, W = 7, P = 18
  • Item 2: P/W = 2.5, W = 2, P = 5
  • Item 4: P/W = 2, W = 5, P = 10

  3. Fill the Knapsack:

  We start filling the knapsack with items in the sorted order until it's full.

  • Item 5:
    • Weight = 3
    • Profit = 12
    • Remaining Capacity: 13 - 3 = 10
  • Item 6:
    • weight = 2
    • Profit = 7
    • Remaining Capacity: 10 - 2 = 8
  • Item 3:
    • Weight = 3
    • Profit = 9
    • Remaining Capacity: 8 - 3 = 5
  • Item 1:
    • Weight = 7
    • Profit = 18
    • Remaining Capacity: 5
    • We can't fit the entire item 1, so we take a fraction of it.
    • Fraction = 5/7
    • Profit from fraction = (5/7) * 18 ≈ 12.86

  4. Calculate Total Profit:

  Total Profit = 12 + 7 + 9 + 12.86 ≈ 40.86

  Solution:

  • Items taken:
    • Item 5: 1.0 (full)
    • Item 6: 1.0 (full)
    • Item 3: 1.0 (full)
    • Item 1: 5/7 (fractional)
  • Total Profit ≈ 40.86                                                                                                                                                                                                                                 {5/7,0,1,0,1,1} with P=40.85                                                     

        TYPE 2: LARGEST PROFIT METHOD

          However, it's crucial to understand that the largest profit method is generally incorrect for the fractional knapsack problem. It doesn't guarantee the optimal solution.

Here's why and then I'll illustrate how it would work, followed by why it fails:

Why the Largest Profit Method Fails:

The Fractional Knapsack problem aims to maximize the total profit per unit weight. Simply picking items with the highest profit ignores the weight associated with that profit. A heavy item with high profit might be less efficient than a lighter item with a slightly lower profit but a much better profit-to-weight ratio.

Illustrating the Largest Profit Method:

Let's apply it to the same problem:

• n = 6
• P = {18, 5, 9, 10, 12, 7}
• W = {7, 2, 3, 5, 3, 2}
• M = 13 (Knapsack capacity)

1. Sort by Profit (Descending):

   • Item 1: P = 18, W = 7
   • Item 5: P = 12, W = 3
   • Item 4: P = 10, W = 5
   • Item 3: P = 9, W = 3
   • Item 6: P = 7, W = 2
   • Item 2: P = 5, W = 2

2. Fill the Knapsack:

   • Item 1:
     • Weight = 7
     • Profit = 18
     • Remaining Capacity: 13 - 7 = 6
   • Item 5:
     • Weight = 3
     • Profit = 12
     • Remaining Capacity: 6 - 3 = 3
   • Item 4:
     • Weight = 5.
     • We can not add the whole item, so we add the fraction.
     • Fraction: 3/5
     • Profit = (3/5) * 10 = 6

3. Total Profit:

   • 18 + 12 + 6 = 36                                                                                                                                                                                                                                                thus feasible solution = {  1, 0, 0 , 3/5 , 1, 0} with P=36

Why This is Suboptimal:

As shown earlier, the optimal solution was approximately 40.86. The largest profit method yielded a result of 36. This is because it prioritized high-profit items without considering their weight efficiency.

In summary:

The largest profit method is simple but not optimal for the Fractional Knapsack problem. The correct approach is to use the profit-to-weight ratio for optimal results.

 "smallest weight" variation. Let's solve both problems with that in mind.

Problem:

• n = 6
• P = {18, 5, 9, 10, 12, 7}
• W = {7, 2, 3, 5, 3, 2}
• M = 13 (Knapsack capacity for standard Fractional Knapsack)
• Smallest Weight: target profit = 39
• TYPE 3.  Standard Fractional Knapsack (Maximize Profit):

• P/W Ratios:
  • 18/7 ≈ 2.57
  • 5/2 = 2.5
  • 9/3 = 3
  • 10/5 = 2
  • 12/3 = 4
  • 7/2 = 3.5
• Sorted Items (P/W descending):
  • Item 5: (12, 3)
  • Item 6: (7, 2)
  • Item 3: (9, 3)
  • Item 1: (18, 7)
  • Item 2: (5, 2)
  • Item 4: (10, 5)
• Fill Knapsack:
  • Item 5: Profit = 12, Weight = 3, Remaining Capacity = 10
  • Item 6: Profit = 7, Weight = 2, Remaining Capacity = 8
  • Item 3: Profit = 9, Weight = 3, Remaining Capacity = 5
  • Item 1: Profit = (5/7) * 18 ≈ 12.86, Weight = 5
• Total Profit: 12 + 7 + 9 + 12.86 ≈ 40.86

TYPE 3 :Smallest Weight Problem (Target Profit = 39):

• Sorted Items (P/W descending): (same as above)
• Fill until Profit >= 39:
  • Item 5: Profit = 12, Weight = 3, Total Profit = 12
  • Item 6: Profit = 7, Weight = 2, Total Profit = 19
  • Item 3: Profit = 9, Weight = 3, Total Profit = 28
  • Item 4: we need 39-28 = 11 more profit.
  • Since Item 4 has a profit of 10, we will need to take 11/10 of item 4. That is impossible.
  • We need 6 more profit.
  • (6/10) * 10 = 6 profit.
  • (3/5) * 10 = 6 profit
  • (3/5) * 5 = 3 weight.
  • Total weight = 3 + 2 + 3 + 3 = 11.
• Total Profit: 12 + 7 + 9 + 6 = 34.
  • This is not 39.
  • We need to take 3/5 of item 4.
  • 12 + 7 + 9 + (3/5 * 10) = 39.
• Total Weight: 3 + 2 + 3 + 3 = 11.

Answers:

• Smallest Weight (Target Profit = 39): Total Weight = 11 thus feasible solution= { 0,1,1,3/5 ,1 ,1) with P=39