Vue.js

Solve the Knapsack Problem Using the Greedy Approach in C

Learn how to tackle the Knapsack Problem with a Greedy Algorithm in C. Detailed code example and explanation included.

The Knapsack Problem is a classic problem in combinatorial optimization, where you aim to maximize the total value of items placed in a knapsack without exceeding its weight capacity. In this blog, we’ll explore a greedy approach to solving this problem using C programming, providing a step-by-step guide and code example.

Implementing the Knapsack Problem Using a Greedy Approach in C

The greedy approach to the Knapsack Problem involves always picking the item with the highest value until the knapsack is full. Here’s a complete C program to demonstrate this:

#include<stdio.h>

int count = 0;
int val[20], wt[20];

int max(int a[], int n) {
    int m = 0;
    count += 2;
    for(int i = 0; i < n; i++) {
        count++;
        if(a[i] > m) {
            count += 2;
            m = a[i];
            val[i] = 0;
        }
        count += 2;
    }
    return m;
}

int knapSack(int W, int wt[], int val[], int n) {
    int pro = 0;
    count++;
    while(W > 0) {
        count++;
        int maxValue = max(val, n);
        if (maxValue == 0) {
            break;
        }
        pro += maxValue;
        W -= wt[val - maxValue]; // Reduce the weight capacity
    }
    count++;
    return pro;
}

void main() {
    int i, n, W;

    printf("Greedy Approach: Knapsack Problem >>\n\n");
    printf("Enter Number of values: ");
    scanf("%d", &n);

    printf("Enter Weight Capacity: ");
    scanf("%d", &W);

    printf("\n\nEnter Profit and Weight Respectively:\n");
    for(i = 0; i < n; i++) {
        printf("\nProfit Weight pair %d\n", 1 + i);
        printf("Profit: ");
        scanf("%d", &val[i]);
        printf("Weight: ");
        scanf("%d", &wt[i]);
    }

    count++;
    printf("\n\nTotal Profit: %d", knapSack(W, wt, val, n));
    printf("\nRequired Steps: %d", count);
}

Explanation:

1. Variable Initialization:
— `count` keeps track of the number of operations.
— `val` and `wt` arrays store the values and weights of the items, respectively.

2. Max Function:
— Finds the maximum value in the `val` array and marks it as used by setting it to 0.
— Updates the `count` for each operation to track the computational steps.

3. KnapSack Function:
— Continually adds the maximum value to the profit (`pro`) while reducing the weight capacity (`W`) until the knapsack is full or no items are left.
— Calls the `max` function to get the highest value item each time.

4. Main Function:
— Takes user input for the number of items, their values, weights, and the weight capacity of the knapsack.
— Calls the `knapSack` function and prints the total profit and required steps.

Conclusion

The greedy approach provides a simple yet effective way to solve the Knapsack Problem, although it may not always yield the optimal solution compared to dynamic programming. This C implementation highlights the method’s straightforward nature and efficiency for certain scenarios. By understanding and utilizing this algorithm, you can enhance your problem-solving skills and tackle more complex optimization problems with confidence. Happy coding!