Knapsack
Problem Statement:
find maximum number of items that can be put in a knapsack of capacity \(W\) from n items with \(i^{th}\) item having weight \(w_i\) and value \(v_i\) .
Algorithm
1. If the total items weigh less than or equal to \(W\) then we include it and not include it and take the maximum of these two knapsack() return values.
2. else ignore this item and return knapsack() of remaining items.
Pseudo code :
knapsack(weight[],value[],w,n):
if n==0 or w==0 :
return 0
if weight[n-1]<=w:
max1 = value[n-1]+knapsack(weight,value,w-weight[n-1],n-1)
max2 = knapsack(weight,value,w,n-1)
maximum = max (max1,max2)
else:
maximum = knapsack(weight,value,w,n-1)
return maximum
Code :
#include <iostream>
using namespace std;
// 0-1 knapsack
/*
input
n w
w[0] w[1] w[2] .... w[n]
v[0] v[1] v[2] .... v[n]
*/
int knapsack(int weight[], int value[], int w, int n)
{
if (n == 0||w==0)
{
return 0;
}
int max1, max2, maximum;
if (weight[n-1] <= w)
{
// max1 = 1 + knapsack(weight, value, w - weight[n], n - 1);
max1 = value[n-1] + knapsack(weight, value, w - weight[n-1], n - 1);
max2 = knapsack(weight, value, w, n - 1);
maximum = max1 > max2 ? max1 : max2;
}
else
{
maximum = knapsack(weight, value, w, n - 1);
}
return maximum;
}
int main()
{
int n, w;
cin >> n >> w;
int weight[n], value[n];
for (int i = 0; i < n; i++)
{
cin >> weight[i];
}
for (int i = 0; i < n; i++)
{
cin >> value[i];
}
cout << "number of items = " << knapsack(weight, value, w, n)<<"\n";
}
Complexity Analysis :
Time complexity: \(O(2^n)\)