/*
Ques.1: Given n objects of different weights, denoted by the set w = {w1, w2, w3, ..., wn} 
and respective profit values denoted by the set p = {p1, p2, p3, ..., pn}. 
Implement an efficient algorithm to select the objects from set 'w' for filling a knapsack having capacity m, 
such that the total sum of weights of selected objects should not exceed the max capacity m and the overall 
profit should be maximized, where each object can be selected only once, and partial selection is not allowed.
Note: Show the output by taking any test case on your own.
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Function to solve 0/1 Knapsack problem
int knapsack(int m, vector<int>& weights, vector<int>& profits, int n) {
    // Create DP table
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    
    // Build the DP table
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= m; w++) {
            if (weights[i - 1] <= w) {
                // Option 1: Include current item
                int include = profits[i - 1] + dp[i - 1][w - weights[i - 1]];
                // Option 2: Exclude current item
                int exclude = dp[i - 1][w];
                dp[i][w] = max(include, exclude);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    
    // Display selected items (backtracking)
    cout << "\nSelected items (index, weight, profit):\n";
    int w = m;
    for (int i = n; i > 0 && w > 0; i--) {
        if (dp[i][w] != dp[i - 1][w]) {
            cout << "Item " << i << ": weight=" << weights[i - 1] 
                 << ", profit=" << profits[i - 1] << endl;
            w -= weights[i - 1];
        }
    }
    
    return dp[n][m];
}

int main() {
    // Test Case
    cout << "=== 0/1 KNAPSACK PROBLEM ===\n";
    vector<int> weights = {2, 3, 4, 5};
    vector<int> profits = {3, 4, 5, 6};
    int m = 8;  // Knapsack capacity
    int n = weights.size();
    
    cout << "Knapsack Capacity: " << m << endl;
    cout << "Items (Weight, Profit):\n";
    for (int i = 0; i < n; i++) {
        cout << "Item " << i + 1 << ": (" << weights[i] << ", " << profits[i] << ")\n";
    }
    
    int maxProfit = knapsack(m, weights, profits, n);
    cout << "\nMaximum Profit Achievable: " << maxProfit << endl;
    
    return 0;
}