The 0/1 Knapsack problem is a classic optimization problem where you have to maximize the total value of items that can fit in a knapsack of a given capacity. Each item can either be included (1) or excluded (0) from the knapsack.

Program Structure

• Input: The weights and values of items, along with the maximum capacity of the knapsack.
• Output: The maximum value that can be carried in the knapsack.
• Dynamic Programming: The program uses a 2D array to store the maximum values for different capacities and items.

C++ Code

#include <iostream>
#include <vector>

using namespace std;

// Function to solve the 0/1 Knapsack problem using dynamic programming
int knapsack(int capacity, const vector<int>& weights, const vector<int>& values, int n) {
    // Create a 2D array to store maximum values
    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));

    // Build the dp array
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= capacity; w++) {
            if (weights[i - 1] <= w) {
                // Include the item
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            } else {
                // Exclude the item
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    // The maximum value is stored in dp[n][capacity]
    return dp[n][capacity];
}

int main() {
    int n, capacity;

    // Input number of items and capacity
    cout << "Enter number of items: ";
    cin >> n;
    cout << "Enter capacity of knapsack: ";
    cin >> capacity;

    vector<int> weights(n), values(n);

    // Input weights and values of items
    cout << "Enter weights of items: ";
    for (int i = 0; i < n; i++) {
        cin >> weights[i];
    }

    cout << "Enter values of items: ";
    for (int i = 0; i < n; i++) {
        cin >> values[i];
    }

    // Calculate the maximum value that can be carried
    int maxValue = knapsack(capacity, weights, values, n);

    // Output the result
    cout << "Maximum value in Knapsack = " << maxValue << endl;

    return 0;
}

Explanation of the Code

The code consists of the following main components:

• Input Handling: The program prompts the user to enter the number of items, their weights, values, and the maximum capacity of the knapsack.
• Knapsack Calculation: The knapsack function implements dynamic programming to fill a 2D array dp. Here, dp[i][w] holds the maximum value that can be attained with a knapsack capacity of w using the first i items.
• Value Inclusion: For each item, the function checks if the weight is less than or equal to the current capacity. If it is, it calculates the maximum value by either including or excluding the item.
• Output: The program displays the maximum value that can be carried in the knapsack.

Conclusion

This program efficiently solves the 0/1 Knapsack problem using dynamic programming techniques, making it suitable for a variety of input sizes while maintaining optimal performance.