0/1
Knapsack Problem
TYPE:Dynamic programming
Problem- Given
some items, pack the knapsack (bag or storage available) to get the maximum total profit. Each item has some weight and some value.
Total weight that we can carry is no more than some fixed number W. So we must
consider weights of items as well as their value.
Example –
W=9
Vi
|
10
|
40
|
50
|
40
|
40
|
50
|
Wi
|
2
|
3
|
4
|
3
|
3
|
4
|
The Bag may not fill completely.
Solution: We can see that there are various ways
through which we can fill our knapsack(bag) while maximizing profit
I.
Taking weights of 2+3+4=9 with profit of 10+40+50 = 100
II.
Taking weights of 3+3+2=8 with profit of 40+40+10 = 90
III.
Taking weights of 4+4=8 with profit of 50+50 = 100
IV.
Taking weights of 3+3+3 =9 with profit of 40+40+40 = 120
Now,
there are many more cases to consider but they certainly have weight less than8
so we are not considering them, so from here the best solution seems to be the
IV. One with bag completely full and profit maximum.
So our main
aim is solving the problem such that the profit is maximum with total weight
less than or equal to knapsack (cannot be greater).
Now, one can think that why leave the bag empty, why
not fill the bag with partial weights like vi=1 etc. So, this thing holds the
catch here, in 0/1 Knapsack, we cannot use fractional weights but absolute ones
only.
Types of Knapsack Problem-
1. 0/1 Knapsack – the item (Vi) is either
used completely or used not at all. We cannot break the item.
2. Fractional Knapsack- The item can be used in
its partial form. We can break the item and use it to fill the bag completely.
Approach for 0/1 Knapsack –
1. Brute Force Approach –
This will take all the
possible subsets over the given items list and evaluate the answer.
Let there be n items so there are 2^n possible subsets. We go through all
the subsets and find that one subset which is having the maximum value and with
total weight less or equal to W(knapsack).
Accomplished using Divide and
Conquer –
We divide the problem into
sub problems and solve them and at last stage we combine the solutions of the
sub problems to find the final answer.
Algorithm
Knapsack, W = total capacity
the person can carry
Array of items, v[0.. n-1] ,
n = #items
Array of corresponding
weights of the items w[0.. n-1]
For every item i, two cases can be considered.
Either we take that item or we do not.
Case 1-
If we do not take item i, then we have maximum for
weight w over the i-1 items, or
Case 2-
if we include item i, then the value of ith item +
recursion over i-1 items with remaining weight (Total weight (W) – weight of
ith item(Wi)). The maximum out of these two cases is our answer.
Knapsackbrute (W, v[], w[], n)
if (W==0 || n==0) // if total weight is
zero , then no items can be
return 0 // included so 0 , or no item is available then also return 0 */
if( w[n-1] >W) // if the weight of the nth item is greater than the
total weight
return knapsackbrute(W,v,w,n-1) // available , then only case 1 can be used and we //recurse over the n-1 subproblems
else
return max( knapsackbrute(W,v,w,n-1),
v[n-1]+knapsackbrute(W-w[n-1],v, w, n-1)
/* both cases considered */
Time
Complexity – O(2^n)
As we are recursing over each possible subset.
Now, the
question arises, how can we better it?
Having subproblems which are not independent
(subproblems share subsubproblems) divide and conquer is expensive and some
method which stores these shared sub problems solution once solved should be
used for better time complexity.
2.
The Dynamic Programming
Approach is
used mostly.
You might wonder why DP and
why not Greedy. Let’s just see the latter first.
Why not Greedy??
The greedy approach says
that the local optimum is the global optimum. Take the best at each stage and
you will end up getting the optimal solution.
Taking above example –
Take Wi
=4 with maximum Vi = 50, remaining weight = 9-4 =5
Now,
again taking most optimal, Wi = 4 with Vi = 50, remaining weight = 5-4 =1
No
item of Wi =1, so stop.
Our answer from this approach = 50+50 = 100.
But as we have already seen that the best solution
is of 120 with weights 3, 3 and 3.
So, the greedy approach won’t work here.
Now to our first question – Why Dynamic Programming?
The answer lies in the very basic properties of DP.
1.
Optimal - Sub Structure- The two cases of divide and
conquer strategy above shows this property. we know that if we take some vith
item having weight wi then the maximum over remaining weight (W-wi) + weight of
vith item gives us the best solution. So the problem jut gets reduced to the
again problem having W-wi weight and n-1 items.
2. Overlapping sub-problems – We already discussed above
that if the sub problems are not independent then DP is always a better
approach, and we know that for using DP the problem must exhibit this essential
property.
Example – W=7 w[]={3, 3,3} n =3
The highlighted portion shows the overlapping sub
problem and hence the DP can be used and will be better.
To reduce time complexity we make a table and store
the solutions of the computed sub problems in it, which can be used later when
bigger problems come.
The two approaches
of DP-
In both the approaches a 2-D table k[n+1][W+1] is
used to store the values for n items and total weight = W.
1. Top Down Approach (Memoization)
Algorithm –
k[n+1][W+1] is declared globally with suitable
values of n & W.
memset(k ,-1, sizeof(k[0][0] * (n+1) * (W+1))); // initialized to -1
intknaptd(int W, int w[] , int v[], int n )
{
if(W<=0 || n<=0) // base case
return
0;
if (k[n][W]! = -1)// if that value has already been computed
return k[n][W];
if(wt[n-1]>W)
return k[n][W] = knaptd(W, w v,n-1); // total weight in this iteration
is less
//than the
weight of the nth item so excluding it
else
return k[n][W] = max (knaptd(W, w, v,n-1),
v[n-1]+knaptd(W-w[n-1], wt , v, n-1) );
}
You may think that this approach is just same as the
divide and conquer approach and YES you are correct, but what makes it dynamic
and its complexity less than the exponential time is that whatever we are
computing through recursion we are storing it in a table for later use.
Bottom – Up approach
k[n+1][W+1] is declared globally with suitable
values of n & W.
int knapsack(int W, int w[], int v[] , int n)
{
int
i , j ; // ith item and jth
weight
memset(k
,0, sizeof(k[0][0] * (n+1) * (W+1)));
for(i=0; i<=n; i++)// as k is a 2-D matrix so just iterate like that for
each item
{ // and for each item take each weight
for(j=0;
j<=W; j++)
{
if(i==0||j==0)// base case
k[i][j]=0
;
else
if(j< w[i-1])// total weight in this iteration
is less
//than the weight of the ith item
k[i][j]
= k[i-1][j]; // not including the ith item
else
k[i][j] = max ( k[i-1][j], v[i-1]+k[i-1][j-w[i-1]]);
// maximum over not //including or including
// with maximum over i-1 items
}
}
return k[n][W];
}
Time
Complexity- O(nW) , as it stores in a 2-D matrix of size (n+1) *(W+1) and this
complexity is much better than the exponential complexity we were getting from
brute force approach.
Even after this the doubts persist, be free to ask
them over our public group-
And if you are among the lucky ones who have got it
, go and solve these problems
Implemenation
of 0/1 Knapsack in C++
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int k[5][60]; // just taken as an example varies as per the problem
// top down using table
intknaptd(int W, int w[] , int v[], int n )
{
if(W<=0 || n<=0)
return 0;
if (k[n][W]!=-1)
return k[n][W];
if(wt[n-1]>W)
return k[n][W] = knaptd(W, w, v,n-1); // total weight in this iteration is less
// than the weight of the ith item so excluding it
else
return k[n][W] = max (knaptd(W, w, v,n-1), v[n-1]+knaptd(W-w[n-1], w , v, n-1) );
}
// Bottom up
int knapsack(int W, int w[], int v[] , int n)
{
int i , j ; // ith item and jth weight
memset(k ,0, sizeof(k[0][0] * (n+1) * (W+1)));
for(i=0; i<=n; i++)
{
for(j=0; j<=W; j++)
{
if(i==0||j==0)
k[i][j]=0 ;
else if(j< w[i-1]) // total weight in this iteration is less than the weight of the ith item
k[i][j] = k[i-1][j]; // not including the ith item
else
k[i][j] = max ( k[i-1][j], v[i-1]+k[i-1][j-w[i-1]]); // maximum over not including or including
// with maximum over i-1 items
}
}
return k[n][W];
}
int main() {
int v[] = {60, 100, 120};
int w[] = {10, 20, 30};
int W = 50;
intn = sizeof(v)/sizeof(v[0]);
printf(“Using Bottom Up Approach”);
printf("%dn", knapsack(W, w, v, n));
printf(“n Using Top down Approach”);
memset(k ,-1, sizeof(k[0][0] * (n+1) * (W+1)));
printf("%dn", knaptd(W, w, v,n));
return 0;
}
