0-1 Knapsack problem | Faceprep

Program to solve the 0-1 knapsack problem is discussed here. Given weights and values of n items, the task is to put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In this problem, 0-1 means that we can either put the complete item in the knapsack or ignore it.

Consider the following example,

Input:
Number of items:3
value and weight of items:
100    20
50       10
150    30
Size of the knapsack:50

Output:
Maximum total value in the knapsack:250

Explanation:

Weight = 20, value = 100
Weight = 10, value = 50
Weight = 30, value = 150
Weight = (20 + 10), Value = (100 + 50)
Weight = (20 + 30), Value = (100 + 150)
Weight = (10 + 30), Value = (50 + 150)
Weight = (20 + 10 + 30) > 50

The maximum among these is 
Weight = (20 + 30), Value = (100 + 150)
Weight = 50, Value = 250

This problem can be solved in two different ways.

Method 1: Naive recursive implementation of 0-1 Knapsack problem.

We have to consider all the subsets of the items.
There can be two cases for each item:

  • Item is included in the optimal subset.
  • Item is not included in the optimal set.

Therefore, the maximum value that can be obtained from the given n items is the max of the following two values.

  • Maximum value obtained by (n-1) items and W weight (by excluding nth item).
  • Value of the nth item plus maximum value obtained by n-1 items and W minus weight of the nth item (by including nth item).

If the weight of the nth item is greater than W, then the nth item cannot be included and case 1 is the only possibility.

Method 2: Dynamic Programming approach of 0-1 knapsack problem.

In this approach, same set of sub-problems are not considered again. It is avoided by creating a temporary array and proceeding to solve in a bottom-up manner.

The time complexity using this approach is  O(n*W), where n is the number of items and W is the weight of the knapsack.

Program to solve 0-1 knapsack problem(Naive approach)

/* C program – Naive recursive implementation of 0-1 Knapsack problem */
#include<stdio.h>

/* Function to find maximum of two integers */
int max(int a, int b) { return (a > b)? a : b; }

/* Function to find the maximum value that can be put in a knapsack of capacity W */
int knapSack(int W, int weight[], int value[], int n)
{
if (n == 0 || W == 0) /* Base Case */
return 0;

/* If weight of the nth item is more than Knapsack capacity W */
if (weight[n-1] > W)
return knapSack(W, weight, value, n-1); /* this item cannot be included in the optimal solution */

else return max( value[n-1] + knapSack(W-weight[n-1], weight, value, n-1), knapSack(W, weight, value, n-1));
}

int main()
{
int n;
printf(“\nEnter the number of items : “);
scanf(“%d”, &n);
int value[n];
int weight[n];
int i;
printf(“\nEnter the item’s weight and its value \n”);
for(i = 0; i < n; i++)
{
scanf(“%d %d”, &weight[i], &value[i]);
}
int W;
printf(“\nEnter the capacity of the knapsack : “);
scanf(“%d”, &W);
printf(“\nMaximum value in a 0-1 knapsack : %d\n”, knapSack(W, weight, value, n));
return 0;
}

/* C++ program – Naive recursive implementation of 0-1 Knapsack problem */
#include<iostream>
using namespace std;

/* Function to find maximum of two integers */
int max(int a, int b) { return (a > b)? a : b; }

/* Function to find the maximum value that can be put in a knapsack of capacity W */
int knapSack(int W, int weight[], int value[], int n)
{
if (n == 0 || W == 0) /* Base Case */
return 0;

/* If weight of the nth item is more than Knapsack capacity W */
if (weight[n-1] > W)
return knapSack(W, weight, value, n-1); /* this item cannot be included in the optimal solution */

else return max( value[n-1] + knapSack(W-weight[n-1], weight, value, n-1), knapSack(W, weight, value, n-1));
}

int main()
{
int n;
cout << “\nEnter the number of items : “;
cin >> n;
int value[n];
int weight[n];
int i;
cout << “\nEnter the item’s weight and its value \n”;
for(i = 0; i < n; i++)
{
cin >> weight[i] >> value[i];
}
int W;
cout << “\nEnter the capacity of the knapsack : “;
cin >> W;
cout << “\nMaximum value in a 0-1 knapsack : ” << knapSack(W, weight, value, n) << endl;
return 0;
}

/* Java program – Naive recursive implementation of 0-1 Knapsack problem */
import java.util.*;
public class Main
{
/* Function to find maximum of two integers */
static int max(int a, int b) { return (a > b)? a : b; }

/* Function to find the maximum value that can be put in a knapsack of capacity W */
static int knapSack(int W, int weight[], int value[], int n)
{
if (n == 0 || W == 0) /* Base Case */
return 0;

/* If weight of the nth item is more than Knapsack capacity W */
if (weight[n-1] > W)
return knapSack(W, weight, value, n-1); /* this item cannot be included in the optimal solution */

else return max( value[n-1] + knapSack(W-weight[n-1], weight, value, n-1), knapSack(W, weight, value, n-1));
}

public static void main (String args[])
{
int n;
Scanner sc = new Scanner(System.in);
System.out.print(“\nEnter the number of items : “);
n = sc.nextInt();
int[] value = new int[n];
int[] weight = new int[n];
int i;
System.out.print(“\nEnter the item’s weight and its value \n”);
for(i = 0; i < n; i++)
{
weight[i] = sc.nextInt();
value[i] = sc.nextInt();
}
int W;
System.out.print(“\nEnter the capacity of the knapsack : “);
W = sc.nextInt();
System.out.print(“\nMaximum value in a 0-1 knapsack : ” + knapSack(W, weight, value, n));
}
}

# Python program – Naive recursive implementation of 0-1 Knapsack problem

def knapSack(W , weight , value , n):
if n == 0 or W == 0 :
return 0

if (weight[n-1] > W):
return knapSack(W , weight , value , n-1)
else:
return max(value[n-1] + knapSack(W-weight[n-1] , weight , value , n-1), knapSack(W , weight , value , n-1))

value = [100, 50, 150]
weight = [20, 10, 30]
W = 50
n = len(val)
print (“Maximum capacity : “,knapSack(W , weight , value , n) )

Program to solve 0-1 knapsack problem(Dynamic Programming approach)

/* C program – Dynamic Programming implementation of 0-1 Knapsack problem */
#include<stdio.h>

/* Function to find maximum of two integers */
int max(int a, int b) { return (a > b)? a : b; }

// Returns the maximum value that can be put in a knapsack of capacity W
int knapSack(int W, int weight[], int value[], int n)
{
int i, w;
int K[n+1][W+1];

/* Build table K[][] in bottom up manner */
for (i = 0; i <= n; i++)
{
for (w = 0; w <= W; w++)
{
if (i==0 || w==0)
K[i][w] = 0;
else if (weight[i-1] <= w)
K[i][w] = max(value[i-1] + K[i-1][w-weight[i-1]], K[i-1][w]);
else
K[i][w] = K[i-1][w];
}
}

return K[n][W];
}

int main()
{
int n;
printf(“\nEnter the number of items : “);
scanf(“%d”, &n);
int value[n];
int weight[n];
int i;
printf(“\nEnter the item’s weight and its value \n”);
for(i = 0; i < n; i++)
{
scanf(“%d %d”, &weight[i], &value[i]);
}
int W;
printf(“\nEnter the capacity of the knapsack : “);
scanf(“%d”, &W);
printf(“\nMaximum value in a 0-1 knapsack : %d\n”, knapSack(W, weight, value, n));
return 0;
}

/* C++ program – Dynamic Programming implementation of 0-1 Knapsack problem */

#include<iostream>
using namespace std;

/* Function to find maximum of two integers */
int max(int a, int b) { return (a > b)? a : b; }

/* Returns the maximum value that can be put in a knapsack of capacity W */
int knapSack(int W, int weight[], int value[], int n)
{
int i, w;
int K[n+1][W+1];

/* Build table K[][] in bottom up manner */
for (i = 0; i <= n; i++)
{
for (w = 0; w <= W; w++)
{
if (i==0 || w==0)
K[i][w] = 0;
else if (weight[i-1] <= w)
K[i][w] = max(value[i-1] + K[i-1][w-weight[i-1]], K[i-1][w]);
else
K[i][w] = K[i-1][w];
}
}

return K[n][W];
}
int main()
{
int n;
cout << “\nEnter the number of items : “;
cin >> n;
int value[n];
int weight[n];
int i;
cout << “\nEnter the item’s weight and its value \n”;
for(i = 0; i < n; i++)
{
cin >> weight[i] >> value[i];
}
int W;
cout << “\nEnter the capacity of the knapsack : “;
cin >> W;
cout << “\nMaximum value in a 0-1 knapsack : ” << knapSack(W, weight, value, n) << endl;
return 0;
}

/* Java program – Dynamic Programming implementation of 0-1 Knapsack problem */

import java.util.*;
public class Main
{
/* Function to find maximum of two integers */
static int max(int a, int b) { return (a > b)? a : b; }

/* Returns the maximum value that can be put in a knapsack of capacity W */
static int knapSack(int W, int weight[], int value[], int n)
{
int i, w;
int[][] K = new int[n+1][W+1];

/* Build table K[][] in bottom up manner */
for (i = 0; i <= n; i++)
{
for (w = 0; w <= W; w++)
{
if (i==0 || w==0)
K[i][w] = 0;
else if (weight[i-1] <= w)
K[i][w] = max(value[i-1] + K[i-1][w-weight[i-1]], K[i-1][w]);
else
K[i][w] = K[i-1][w];
}
}

return K[n][W];
}
public static void main (String args[])
{
int n;
Scanner sc = new Scanner(System.in);
System.out.print(“\nEnter the number of items : “);
n = sc.nextInt();
int[] value = new int[n];
int[] weight = new int[n];
int i;
System.out.print(“\nEnter the item’s weight and its value \n”);
for(i = 0; i < n; i++)
{
weight[i] = sc.nextInt();
value[i] = sc.nextInt();
}
int W;
System.out.print(“\nEnter the capacity of the knapsack : “);
W = sc.nextInt();
System.out.print(“\nMaximum value in a 0-1 knapsack : ” + knapSack(W, weight, value, n));
}
}

# Python program – Dynamic Programming implementation of 0-1 Knapsack problem

def knapSack(W, weight, value, n):
K = [[0 for x in range(W+1)] for x in range(n+1)]

# Build table K[][] in bottom up manner
for i in range(n+1):
for w in range(W+1):
if i==0 or w==0:
K[i][w] = 0
elif weight[i-1] <= w:
K[i][w] = max(value[i-1] + K[i-1][w-weight[i-1]], K[i-1][w])
else:
K[i][w] = K[i-1][w]

return K[n][W]

value = [100, 50, 150]
weight = [20, 10, 30]
W = 50
n = len(val)
print (“Maximum capacity : “,knapSack(W , weight , value , n) )

Output:

0-1 knapsack problem