Fractional Knapsack Problem

Problem Statement

Suppose there are n items. Each item has a weight w_i and a profit p_i. The knapsack has a maximum capacity of W. We have to select items such that the total weight does not exceed W and the total profit is maximum.

Maximize Total Profit

Subject to: Total Weight ≤ Knapsack Capacity

Types of Knapsack Problem

The Knapsack Problem can be classified according to how many times an item can be selected and whether an item can be divided.

Basic Difference Between the Types

Knapsack Problem Structure

                         KNAPSACK PROBLEM
                                |
          +---------------------+---------------------+
          |                     |                     |
          v                     v                     v
     Fractional             0/1 Knapsack       Repetition Allowed
          |                     |                     |
          v                     v             +-------+-------+
       Greedy               Dynamic            |               |
                             Programming        v               v
                                           Bounded         Unbounded
                                             |               |
                                             v               v
                                      Limited Copies   Unlimited Copies

Important Terms

1. Fractional Knapsack Problem

In the Fractional Knapsack Problem, an item can be divided into smaller portions. If the complete item cannot fit into the knapsack, a fraction of that item can be selected.

The Fractional Knapsack Problem is optimally solved using the Greedy Method. Items are arranged according to their Profit/Weight ratio in descending order.

Working Principle of Fractional Knapsack

Profit/Weight Ratio = Profit ÷ Weight

1. Calculate the Profit/Weight ratio for every item.
2. Sort the items in descending order of the ratio.
3. Select the item having the highest ratio.
4. If the complete item fits, select it completely.
5. If it does not fit, select only the required fraction.
6. Continue until the knapsack becomes full.

Fractional Knapsack: Solved Example 1

Knapsack capacity = 50 kg

Step 1: Sort According to Profit/Weight

A → B → C

Step 2: Fill the Knapsack

Profit obtained from C:

120 × 20/30 = ₹80

Maximum Profit = ₹240

Fractional Knapsack: Solved Example 2

Knapsack capacity = 60 kg

Sorted order:

C → A → B → D

Maximum Profit = 60 + 100 + 120 = ₹280

Fractional Knapsack: Solved Example 3

Knapsack capacity = 50 kg

Order:

A → B → C

Take A and B completely:

Weight = 10 + 20 = 30 kg

Profit = ₹100 + ₹120 = ₹220

Remaining capacity = 20 kg. Only 20 kg of C can be selected.

Fraction = 20/30 = 2/3

Profit from C = 150 × 2/3 = ₹100

Maximum Profit = ₹320

Fractional Knapsack Algorithm

Complexity of Fractional Knapsack

2. 0/1 Knapsack Problem

In the 0/1 Knapsack Problem, an item cannot be divided and cannot be selected more than once. Every item has exactly two possibilities:

0 → Item is not selected

1 → Item is selected completely

Dynamic Programming is commonly used because the problem has overlapping subproblems and optimal substructure.

0/1 Knapsack Formula

Let DP[i][w] represent the maximum profit obtained using the first i items with capacity w.

If the item is too heavy:

DP[i][w] = DP[i−1][w]

Otherwise:

DP[i][w] = max(DP[i−1][w], p_i + DP[i−1][w−w_i])

0/1 Knapsack: Solved Example 1

Knapsack capacity = 50 kg

Possible Valid Combinations

The last combination is invalid because its weight is 60 kg, which exceeds the capacity.

Maximum Profit = ₹220

Selected Items = 2 and 3

0/1 Knapsack: Solved Example 2

Capacity = 5 kg

Maximum Profit = 7

Selected Items = 1 and 2

0/1 Knapsack: Solved Example 3

Capacity = 7 kg

Maximum Profit = ₹9

Selected Items = B and C

0/1 Knapsack Dynamic Programming Algorithm

Complexity of 0/1 Knapsack

3. Bounded Knapsack Problem

In the Bounded Knapsack Problem, items cannot be divided, but each item has a limited number of available copies. Therefore, an item may be selected more than once, but only up to its specified quantity.

For example, if an item has a maximum quantity of 3, it may be selected:

0, 1, 2, or 3 times

but it cannot be selected 4 times.

Bounded Knapsack Example 1

Knapsack capacity = 10 kg

Step 1: Examine Valid Quantities

The combination B + B + C is invalid because its weight is 11 kg, exceeding the capacity of 10 kg.

The best valid combination is:

A + B + C

Weight = 2 + 3 + 5 = 10 kg

Profit = 3 + 4 + 7 = ₹14

Maximum Profit = ₹14

Bounded Knapsack Example 2

Knapsack capacity = 12 kg

Important Valid Combinations

The maximum valid selection is:

3A + 2B

Weight = 3(2) + 2(3) = 12 kg

Profit = 3(6) + 2(7) = ₹32

Maximum Profit = ₹32

Bounded Knapsack Example 3

Knapsack capacity = 15 kg

Compare Important Selections

Therefore:

Selected Items = A + B + C

Weight = 3 + 5 + 7 = 15 kg

Maximum Profit = ₹36

Bounded Knapsack Dynamic Programming

The Bounded Knapsack Problem can be solved using Dynamic Programming by considering the number of copies of each item that can be selected. For item i, let its maximum available quantity be q_i. For a capacity w, we can consider selecting:

0, 1, 2, ..., q_i

copies, provided that the total weight does not exceed the capacity.

The recurrence can be written as:

DP[i][w] = max_{0 ≤ k ≤ qi} { k × p_i + DP[i−1][w − k × w_i] }

where k is the number of copies of item i selected.

Bounded Knapsack Algorithm

Complexity of Bounded Knapsack

Here, Q represents the maximum quantity considered for an item.

4. Unbounded Knapsack Problem

In the Unbounded Knapsack Problem, items cannot be divided, but an item can be selected an unlimited number of times. There is no fixed upper quantity for an item.

If an item weighs 2 kg, it may be selected:

0, 1, 2, 3, 4, ... times

as long as the total weight does not exceed the knapsack capacity.

Unbounded Knapsack: Solved Example 1

Knapsack capacity = 7 kg

Valid Combinations

The best selection is:

A + A + B

Weight = 2 + 2 + 3 = 7 kg

Profit = 3 + 3 + 4 = ₹10

Maximum Profit = ₹10

Unbounded Knapsack: Solved Example 2

Knapsack capacity = 20 kg

Important Valid Combinations

The best selection is B + B:

Weight = 10 + 10 = 20 kg

Profit = 30 + 30 = ₹60

Maximum Profit = ₹60

Unbounded Knapsack: Solved Example 3

Knapsack capacity = 10 kg

Important Valid Combinations

Maximum Profit = ₹14

Selected Items = C + C

Dynamic Programming Formula for Unbounded Knapsack

Let DP[w] represent the maximum profit that can be obtained with capacity w.

DP[w] = max(DP[w], profit[i] + DP[w − weight[i]])

The important difference from 0/1 Knapsack is that the state DP[w − weight[i]] can already contain the same item. Therefore, the same item can be selected again.

Unbounded Knapsack Algorithm

Complexity of Unbounded Knapsack

Bounded vs Unbounded Knapsack

Complete Comparison of Knapsack Types

How to Identify the Knapsack Type

Fractional → Divide    |    0/1 → Take or Leave    |    Bounded → Limited Copies    |    Unbounded → Unlimited Copies

Applications of Knapsack Problem

Summary

The Knapsack Problem requires selecting items to maximize profit while keeping the total weight within a fixed capacity. The four important forms are Fractional, 0/1, Bounded and Unbounded Knapsack.

In Fractional Knapsack, items can be divided and the Greedy Method based on Profit/Weight ratio provides an optimal solution. In 0/1 Knapsack, each item can be selected at most once. In Bounded Knapsack, each item can be selected only up to a specified quantity. In Unbounded Knapsack, an item can be selected unlimited times.

Fractional → Greedy → Items can be divided

0/1 → Dynamic Programming → Take once or leave

Bounded → Dynamic Programming → Limited copies

Unbounded → Dynamic Programming → Unlimited copies