IndianTechnoEra: Knapsack Problem Solution using Greedy Approach | DAA

Solving the Knapsack Problem using Greedy Approach

What is the Knapsack Problem?

The knapsack problem is a classic optimization problem in computer science. Given a set of items, each with a weight and a value, determine which items to include in a collection (knapsack) so that:

1. The total weight is less than or equal to a given limit (knapsack capacity)
2. The total value is as large as possible

Types of Knapsack Problems

There are several variations of the knapsack problem:

• 0/1 Knapsack: Items cannot be divided - you either take the whole item or leave it.
• Fractional Knapsack: Items can be divided, allowing fractions of items to be taken (this is the version suitable for the greedy approach).
• Unbounded Knapsack: Multiple instances of the same item can be included.

Example

Consider we have two items:

• Item 1: 2kg weight, value ₹3
• Item 2: 3kg weight, value ₹4

0/1 Knapsack: We cannot pick 1kg from the 2kg item - we must take it completely or not at all.

Fractional Knapsack: We can take a portion of an item (like 1.5kg of the 3kg item).

Greedy Approach to Fractional Knapsack

The greedy approach is particularly effective for the fractional knapsack problem. Here's how it works:

1. Calculate the value-to-weight ratio for each item (value per unit weight)
2. Sort the items in decreasing order of this ratio
3. Start adding items from the top of the sorted list
4. If an item can't fit completely, take a fraction of it to fill the remaining capacity

Note: While the greedy approach provides an optimal solution for the fractional knapsack problem, it doesn't guarantee an optimal solution for the 0/1 knapsack problem. For 0/1 knapsack, dynamic programming is typically used.

C Program Implementation Simple Version

Here's a C program that solves the fractional knapsack problem using the greedy approach:

#include <stdio.h>

void main()
{
    int capacity, no_items, cur_weight, item;
    int used[10];
    float total_profit;
    int i;
    int weight[10];
    int value[10];


    printf("\nAim: Solution of Knapsack problem using Greedy Approach in C");
    printf("\nUser Input: By user");
    printf("\n==============================================\n");

    printf("Enter the capacity of knapsack:\n");
    scanf("%d", &capacity);

    printf("Enter the number of items:\n");
    scanf("%d", &no_items);

    printf("Enter the weight and value of %d item:\n", no_items);
    for (i = 0; i < no_items; i++)
    {
        printf("Weight[%d]:\t", i);
        scanf("%d", &weight[i]);
        printf("Value[%d]:\t", i);
        scanf("%d", &value[i]);
    }

    for (i = 0; i < no_items; ++i)
        used[i] = 0;

    cur_weight = capacity;
    while (cur_weight > 0)
    {
        item = -1;
        for (i = 0; i < no_items; ++i)
            if ((used[i] == 0) &&
                ((item == -1) || ((float) value[i] / weight[i] > (float) value[item] / weight[item])))
                item = i;

        used[item] = 1;
        cur_weight -= weight[item];
        total_profit += value[item];
        if (cur_weight >= 0)
            printf("Added object %d (%d Rs., %dKg) completely in the bag. Space left: %d.\n", item + 1, value[item], weight[item], cur_weight);
        else
        {
            int item_percent = (int) ((1 + (float) cur_weight / weight[item]) * 100);
            printf("Added %d%% (%d Rs., %dKg) of object %d in the bag.\n", item_percent, value[item], weight[item], item + 1);
            total_profit -= value[item];
            total_profit += (1 + (float)cur_weight / weight[item]) * value[item];
        }
    }

    printf("Filled the bag with objects worth %.2f Rs.\n", total_profit);
    
    int hold;
    scanf("%d",&hold);
}

C Program Implementation

Here's a well-structured C program that solves the fractional knapsack problem using the greedy approach:

#include <stdio.h>

// Structure to represent an item
typedef struct {
    int weight;
    int value;
    float ratio;  // value-to-weight ratio
    int index;    // original index
} Item;

// Function to sort items in descending order of value-to-weight ratio
void sortItems(Item items[], int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (items[j].ratio < items[j+1].ratio) {
                Item temp = items[j];
                items[j] = items[j+1];
                items[j+1] = temp;
            }
        }
    }
}

int main() {
    int capacity, no_items;
    Item items[10];
    float total_value = 0.0;
    
    printf("\nKnapsack Problem Solution using Greedy Approach in C\n");
    printf("====================================================\n\n");
    
    // Get user input
    printf("Enter the capacity of knapsack (in Kg): ");
    scanf("%d", &capacity);
    
    printf("Enter the number of items: ");
    scanf("%d", &no_items);
    
    printf("\nEnter weight and value for each item:\n");
    for (int i = 0; i < no_items; i++) {
        printf("Item %d:\n", i+1);
        printf("  Weight (Kg): ");
        scanf("%d", &items[i].weight);
        printf("  Value (Rs.): ");
        scanf("%d", &items[i].value);
        items[i].ratio = (float)items[i].value / items[i].weight;
        items[i].index = i+1;
    }
    
    // Sort items based on value-to-weight ratio
    sortItems(items, no_items);
    
    printf("\nProcessing items in order of highest value per Kg...\n");
    
    // Fill the knapsack
    int remaining_capacity = capacity;
    for (int i = 0; i < no_items && remaining_capacity > 0; i++) {
        if (items[i].weight <= remaining_capacity) {
            // Take the whole item
            printf("Added item %d (%d Rs., %d Kg) completely. Space left: %d Kg.\n",
                   items[i].index, items[i].value, items[i].weight, 
                   remaining_capacity - items[i].weight);
            total_value += items[i].value;
            remaining_capacity -= items[i].weight;
        } else {
            // Take a fraction of the item
            float fraction = (float)remaining_capacity / items[i].weight;
            printf("Added %.2f%% of item %d (%d Rs., %d Kg).\n",
                   fraction * 100, items[i].index, items[i].value, items[i].weight);
            total_value += fraction * items[i].value;
            remaining_capacity = 0;
        }
    }
    
    printf("\nFinal Result:\n");
    printf("Filled the knapsack with items worth %.2f Rs.\n", total_value);
    
    return 0;
}

Example Output

Knapsack Problem Solution using Greedy Approach in C
====================================================

Enter the capacity of knapsack (in Kg): 50
Enter the number of items: 3

Enter weight and value for each item:
Item 1:
  Weight (Kg): 10
  Value (Rs.): 60
Item 2:
  Weight (Kg): 20
  Value (Rs.): 100
Item 3:
  Weight (Kg): 30
  Value (Rs.): 120

Processing items in order of highest value per Kg...
Added item 1 (60 Rs., 10 Kg) completely. Space left: 40 Kg.
Added item 2 (100 Rs., 20 Kg) completely. Space left: 20 Kg.
Added 66.67% of item 3 (120 Rs., 30 Kg).

Final Result:
Filled the knapsack with items worth 240.00 Rs.

Explanation of the Solution

Let's break down how the program works with the example input:

1. Input: Knapsack capacity = 50kg, 3 items with weights and values:
   • Item 1: 10kg, ₹60
   • Item 2: 20kg, ₹100
   • Item 3: 30kg, ₹120
2. Calculate Ratios:
   • Item 1: 60/10 = ₹6 per kg
   • Item 2: 100/20 = ₹5 per kg
   • Item 3: 120/30 = ₹4 per kg
3. Sort Items: The items are processed in order: Item 1, Item 2, Item 3
4. Add Items:
   • Add all of Item 1 (10kg): Capacity left = 40kg, Total value = ₹60
   • Add all of Item 2 (20kg): Capacity left = 20kg, Total value = ₹160
   • Add 20/30 = 2/3 of Item 3: Adds ₹80 (2/3 of ₹120), Total value = ₹240

Advantages of the Greedy Approach

• Simple and easy to implement
• Efficient with time complexity of O(n log n) due to sorting
• Guaranteed to find the optimal solution for fractional knapsack

Limitations

• Doesn't work for the 0/1 knapsack problem (where items can't be divided)
• Requires sorting all items, which adds to the time complexity

Practical Applications: The knapsack problem has numerous real-world applications including resource allocation, investment portfolio optimization, inventory management, and budget allocation problems.

Post Key: Analysis of Data Structure Algorithm, Design and Analysis of Data Structure Algorithm, Data Structure, ADA, DAA