#include <stdio.h>
int n, W, w[10], v[10], V[10][10], x[10];
int max(int a, int b) 
{
    if(a>b)
        return a;
    else
        return b;
}

void knapsack() 
{
    int i, j;
    for (i = 0; i <= n; i++) 
    {
        for (j = 0; j <= W; j++) 
        {
            if (i == 0 || j == 0) 
            {
                V[i][j] = 0;
            } 
            else if (j < w[i]) 
            {
                V[i][j] = V[i - 1][j];
            } 
            else 
            {
                V[i][j] = max(V[i - 1][j], V[i - 1][j - w[i]] + v[i]);
            }
            printf("%d\t", V[i][j]);
        }
        printf("\n\n");
    }
}

void printsolution() 
{
    int i = n, j = W;
    while (i != 0 && j != 0) 
    {
        if (V[i][j] != V[i - 1][j]) 
        {
            x[i] = 1;
            j = j - w[i];
        } 
        else 
        {
            x[i] = 0;
        }
        i--;
    }
}

int main() 
{
    int i;
    printf("Enter number of objects\n");
    scanf("%d", &n);
    printf("Enter knapsack capacity\n");
    scanf("%d", &W);
    printf("Enter weights of the objects\n");
    for (i = 1; i <= n; i++) 
    {
        scanf("%d", &w[i]);
    }
    printf("Enter profits of the objects\n");
    for (i = 1; i <= n; i++) 
    {
        scanf("%d", &v[i]);
    }
    knapsack();
    printsolution();
    printf("Object\tWeight\tProfit\n\n");
    for (i = 1; i <= n; i++) 
    {
        if (x[i] == 1) 
        {
            printf("%d\t%d\t%d\n\n", i, w[i], v[i]);
        }
    }
    printf("Maximum Profit is %d\n", V[n][W]);
    return 0;
}