/* 6(a). W.A.P. to implement the knapsack problem using dynamic programming.*/

#include<stdio.h>
#include<conio.h>
int n,cap,w[10],p[10],x[10];
int Max(int a, int b)
{
    return ((a < b) ? b : a);
}
int Knap(int i, int y)
{
    if (i == n) return ((y < w[n]) ? 0 : p[n]);
        if (y < w[i]) return Knap(i+1,y);
            else return (Max(Knap(i+1,y),Knap(i+1,y-w[i]) + p[i]));
}
void TraceBack(void)
{
    int i,c=cap;
        for (i = 1; i < n; i++)
        {
            if (Knap(i, c) == Knap(i + 1, c))
                x[i] = 0;
            else
            {    
                x[i] = 1;
                c -= w[i];
            }
        }
        x[n] = (Knap(n, c)) ? 1 : 0;
}
void main()
{
    int i;
    clrscr();
    printf("Enter the no. of objects : ");
    scanf("%d",&n);
    printf("\nEnter the capacity of Knapsack : ");
    scanf("%d",&cap);
    printf("\nEnter the weight & profit of the %d objects :\n",n);
        for (i = 1; i <= n; i++)
        {
            printf("\nEnter wt. of %d object : ",i);
            scanf("%d",&w[i]);
            printf("Enter profit of %d object : ",i);
            scanf("%d",&p[i]);
        }
        printf("\n\nResult is %d",Knap(1,cap));
        TraceBack();
        printf("\nThe selected elements are :\n");
        for (i = 1; i <= n; i++)
            printf("%d ",x[i]);
        getch();
}
/* OUTPUT
Enter the no. of objects : 3
Enter the capacity of Knapsack : 6
Enter the weight & profit of the 4 objects :

Enter wt. of 1 object : 4
Enter profit of 1 object : 9

Enter wt. of 2 object : 5
Enter profit of 2 object : 10

Enter wt. of 3 object : 2
Enter profit of 3 object : 7

Result is 13
The selected elements are :
1 0 1
*/