01Knap.cpp

#include <iostream>
using namespace std;

class Knapsack {
    int n, capacity;
    int *weights, *values, **dp;

public:
    Knapsack(int items, int cap) {
        n = items;
        capacity = cap;

        // Dynamically allocate arrays
        weights = new int[n];
        values = new int[n];

        // Dynamic allocation for DP table
        dp = new int*[n + 1];
        for (int i = 0; i <= n; i++)
            dp[i] = new int[capacity + 1];

        // Initialize DP table with 0
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= capacity; j++)
                dp[i][j] = 0;
    }

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

    void solveKnapsack() {
        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= capacity; w++) {
                if (weights[i - 1] <= w) {
                    int includeItem = values[i - 1] + dp[i - 1][w - weights[i - 1]];
                    int excludeItem = dp[i - 1][w];

                    // Replacing max function manually
                    if (includeItem > excludeItem)
                        dp[i][w] = includeItem;
                    else
                        dp[i][w] = excludeItem;
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }
    }

    void printSolution() {
        cout << "Maximum value in Knapsack: " << dp[n][capacity] << endl;
    }

    ~Knapsack() {
        // Free dynamically allocated memory
        delete[] weights;
        delete[] values;
        for (int i = 0; i <= n; i++)
            delete[] dp[i];
        delete[] dp;
        cout << "Memory freed\n";
    }
};

int main() {
    int n, capacity;
    cout << "Enter number of items and knapsack capacity: ";
    cin >> n >> capacity;

    Knapsack knapsack(n, capacity);
    knapsack.inputItems();
    knapsack.solveKnapsack();
    knapsack.printSolution();

    return 0;
}