0/1 KNAPSACK C PROGRAM

/*CSEMATTER.BLOGSPOT.IN

Program:C Program to implement 0/1 Knapsack*/


#include<stdio.h>
#include<conio.h>
int main()
{
    int i,j,n,w[20],v[20],W,c[10][10];
    printf("Enter the no. of entities ");
    scanf("%d",&n);
    printf("Enter the no. of entities of each items");
    for(i=0; i<n; i++)
        scanf("%d",&w[i]);
    printf("Enter respective costs of entities");
    for(i=0; i<n; i++)
        scanf("%d",&v[i]);
    printf("Enter the capacity of knapsack: ");
    scanf("%d",&W);

    for(i=0;i<=W;i++)
    c[0][i]=0;
    for(i=1;i<=n;i++)
    c[i][0]=0;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=W;j++)
        {
            if(w[i]<=j)
            {
                if((v[i]+c[i-1][j-w[i]])>c[i-1][j])
                c[i][j]=v[i]+c[i-1][j-w[i]];
                else
                {c[i][j]=c[i-1][j];}
            }
            else
            {c[i][j]=c[i-1][j];}
        }
    }
    for(i=0;i<=n;i++)
    {
        for(j=0;j<=W;j++)
        {
            printf("%d \t",c[i][j]);
        }
        printf("\n");
    }
    printf("Value of maximum profit entity for knapsack is: %d",c[n][W]);
    getch();
}

/*OUTPUT:
Enter the no. of entities 4
Enter the no. of entities of each items2
3
4
5
Enter respective costs of entities3
4
5
6
Enter the capacity of knapsack: 5
0       0       0       0       0       0
0       0       3       3       3       3
0       0       3       4       4       7
0       0       3       4       5       7
0       0       3       4       5       7
Value of maximum profit entity for knapsack is: 7   */