Lab program 4: Implement 0/1 Knapsack problem using Dynamic Programming.

Description:

Problem Statement: A thief robbing a store and can carry a maximal weight of W into their knapsack. There are n items and i^th  item weigh w and is worth v dollars. What items should thief take?

There are two versions of problem

Fractional knapsack problem:    The setup is same, but the thief can take fractions of items, meaning that the items can be broken into smaller pieces so that thief may decide to carry only a fraction of xi of item i, where 0 ≤ xi ≤ 1.

0-1 knapsack problem:    The setup is the same, but the items may not be broken into smaller pieces, so thief may decide either to take an item or to leave it (binary choice), but may not take a fraction of an item.

Dynamic-Programming Solution to the 0-1 Knapsack Problem:

Let i be the highest-numbered item in an optimal solution S for W pounds. Then S` = S - {i} is an optimal solution for W - wi pounds and the value to the solution S is Vi plus the value of the subproblem.

We can express this fact in the following formula: define c[i, w] to be the solution for items  1,2, . . . , i and maximum weight w. Then

	0	if i = 0 or w = 0
c[i,w]  =	c[i-1, w]	if wi ≥ 0
	max [vi + c[i-1, w-wi], c[i-1, w]}	if i>0 and w ≥  wi

Solution:

#include<stdio.h>

void kpsk(int ,int ,int[],int[],int[][100]);

void opt(int,int,int[],int[][100]);

int max(int,int);

void main()

{

            int w[20],p[20],n,m,i,v[10][100];

            printf("Enter the no of elements\n");

            scanf("%d",&n);

            printf("Enter the capacity of knapsack\n");

            scanf("%d",&m);

            printf("Enter the weight of elements\n");

            for(i=1;i<=n;i++)

                        scanf("%d",&w[i]);

            printf("Enter the profit of elements\n");

            for(i=1;i<=n;i++)

            {

                        scanf("%d",&p[i]);

            }

            kpsk(n,m,w,p,v);

            opt(n,m,w,v);

}

void kpsk(int n,int m,int w[],int p[],int v[][100])

{

            int i,j;

            for(i=0;i<=n;i++)

            for(j=0;j<=m;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],p[i]+v[i-1][j-w[i]]);

            }

            for(i=0;i<=n;i++)

            {

                        for(j=0;j<=m;j++)

                        {

                                    printf("%d\t",v[i][j]);

                        }

                        printf("\n");

            }

}

void opt(int n,int m,int w[],int v[][100])

{

            int i,j,x[10];

            printf("The optimal solution is %d\n",v[n][m]);

            for(i=0;i<n;i++)

            x[i]=0;

            i=n;

            j=m;

            while((i!=0)&& (j!=0))

            {

                        if(v[i][j]!=v[i-1][j])

                        {

                                    x[i]=1;

                                    j=j-w[i];

                        }

                        i=i-1;

            }

            printf("The objects selected are \n");

            for(i=1;i<=n;i++)

            {

                        if(x[i]==1)

                                    printf("%d ",i);

            }

 }

 int max(int a, int b)

 {

            return(a>b? a:b);

 }

OUTPUT :

enter the no of elements

4

enter the capacity of knapsack

5

enter the wt of elements

2 1 3 2

enter the profit of elements

12 10 20 15

0       0       0       0       0       0

0       0       12      12      12      12

0       10      12      22      22      22

0       10      12      22      30      32

0       10      15      25      30      37

The optimal solution is 37

The objects selected are 1 2 4