Program Overview

This program solves the 0/1 knapsack problem using dynamic programming. In this problem, we are given a set of items, each with a weight and a value, and a knapsack with a maximum weight capacity. The goal is to determine the maximum value that can be obtained by selecting items without exceeding the weight capacity.

Program Structure

• Input: Number of items, their weights, values, and the maximum weight capacity of the knapsack.
• Dynamic Programming Table: A 2D array to store the maximum values at each capacity for the items considered.
• Output: The maximum value that can be obtained within the weight limit.

C Program

#include 

// Function to solve the 0/1 Knapsack problem
int knapsack(int capacity, int weights[], int values[], int n) {
    int K[n + 1][capacity + 1]; // DP table

    // Build the table in bottom-up manner
    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= capacity; w++) {
            if (i == 0 || w == 0) {
                K[i][w] = 0; // Base case: no items or zero capacity
            } else if (weights[i - 1] <= w) { // Item can be included K[i][w] = (values[i - 1] + K[i - 1][w - weights[i - 1]] > K[i - 1][w]) ? 
                          (values[i - 1] + K[i - 1][w - weights[i - 1]]) : K[i - 1][w];
            } else {
                // Item cannot be included
                K[i][w] = K[i - 1][w];
            }
        }
    }

    return K[n][capacity]; // Maximum value in the knapsack
}

// Main function
int main() {
    int n, capacity;

    // Input number of items and maximum capacity
    printf("Enter the number of items: ");
    scanf("%d", &n);
    printf("Enter the capacity of the knapsack: ");
    scanf("%d", &capacity);

    int weights[n], values[n];

    // Input weights and values of the items
    printf("Enter the weights of the items:\n");
    for (int i = 0; i < n; i++) {
        scanf("%d", &weights[i]);
    }
    
    printf("Enter the values of the items:\n");
    for (int i = 0; i < n; i++) {
        scanf("%d", &values[i]);
    }

    // Calculate the maximum value
    int maxValue = knapsack(capacity, weights, values, n);
    printf("Maximum value in the knapsack: %d\n", maxValue);

    return 0;
}

Explanation of the Code

The program consists of two main parts: the function for solving the knapsack problem and the main function to handle input and output:

• The knapsack function implements the dynamic programming approach:
  • A 2D array K is created to store the maximum values for different capacities and items.
  • The function iterates through each item and each weight capacity, filling in the table based on whether the current item can be included in the knapsack.
  • If the item can be included, it checks whether including it yields a higher value than excluding it, and updates the table accordingly.
• The main function handles user input:
  • The user is prompted to enter the number of items and the maximum capacity of the knapsack.
  • It then inputs the weights and values of the items and calls the knapsack function to compute the maximum value.

Usage

To use the program:

1. Compile the program using a C compiler (e.g., gcc).
2. Run the executable and input the number of items and the capacity of the knapsack.
3. Input the weights and values of the items.
4. The program will output the maximum value that can be obtained without exceeding the weight capacity.