Knapsack

/// Header file begin
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <string>
#include <vector>
#include <cmath>
#include <cctype>
#include <sstream>
#include <set>
#include <list>
#include <stack>
#include<utility>
#include <queue>
#include <algorithm>
#define pf printf
#define sf scanf

/// Macros for Graph

#define white 0
#define gray 1
#define black -1
#define nil -2

using namespace std;

int dp[100][100],backtrack[100][100];

struct my
{
    int weight;
    int price;
};

my ar[100];

void print_element(int i, int j)
{
    if(dp[i][j] == 0)
    {
        return;
    }

    if(backtrack[i][j] == 1)
    {
        print_element(i-1,j-ar[i].weight);
        pf("%d ",i);
    }

    else
    {
        print_element(i-1,j);
    }
}



int main()
{
//    mem(dp,0);
    int maximum_weight, item;

    //cin >> maximum_weight >> item;
    pf("Enter maximum weight and no. of item: ");
    sf("%d %d",&maximum_weight,&item);

        pf("Enter weight and their Price:\n");

        for(int i=1;i<=item;i++)
        {
            cin >> ar[i].weight >> ar[i].price;
        }

        for(int i=1;i<=item;i++)
        {
            for(int j=1;j<=maximum_weight;j++)
            {
                if(ar[i].weight <= j)
                {
                    //dp[i][j] = max(dp[i-1][j], (ar[i].price + (dp[i-1][j-ar[i].weight])));
                    int a=dp[i-1][j] , b = ar[i].price + (dp[i-1][j-ar[i].weight]);

                    if(a>=b)
                    {
                        dp[i][j] = a;
                        backtrack[i][j] = 0;
                    }

                    else
                    {
                        dp[i][j] = b;
                        backtrack[i][j] = 1;
                    }
                }

                else
                {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }

        pf("Knapsack Matrix:\n");

        for(int i=0;i<=item;i++)
        {
            for(int j=0;j<=maximum_weight;j++)
            {
                cout << dp[i][j] << " ";
            }

            pf("\n");
        }

        pf("Answer: %d\nElements are: ",dp[item][maximum_weight]);

        print_element(item,maximum_weight);
    //}

    return 0;
}