23 Sept 2013

Knapsack Problem

Problem Statement: 
                Find  the maximum value for the given capacity of Knapsack.
       Input vectors are :
     


Values (v)
15
9
5
10
Weights (w)
1
3
4
5

Knapsack Capacity  (C) :    8


Solution:

This problem involves filling the knapsack with objects with maximum value.
Inputs to the problem are Values , Weights of the objects and the knapsack capacity.
You have to pick up the objects from the given set such that total weight of the objects is utmost the capacity of knapsack.

 Optimal Sub-Structure Equation:




V(i,W) = V(i -1 , W )       ,  If  wi > W
             = V(i – 1 , W)      , not choosing the ith term
             = vi + V(i -1 , W – wi) ,  choosing the ith term


Solution of the given problem is in the figure given below using 2-D matrix




 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/**
 * Modifed Knapsack, using already computed values 
 * from the matrix by simple lookups
 * @author Prateek
 *
 */
public class KnapSack2 {
 
 int[] values;
 int[] weights;
 int capacity;  //max capacity allowed in knapsack
 int numObjects;
 Integer[][] matrix;  // matrix to for easy looks ups
 
 
 
 public KnapSack2(int[] values, int[] weights, int capacity) {
   this.values=values;
   this.weights=weights;
   this.capacity=capacity;
   this.matrix=new Integer[capacity+1][values.length + 1 ];
   this.numObjects=values.length -1  ;
 }
 
 /**
  * KnapSack procedure, using table loopups to enhance performance
  * @return max profit with given capacity
  */
 public int knapSack(int currentCapacity, int item) {
  
  if(item > numObjects) 
  {
   matrix [ currentCapacity ] [ item ] = 0;
   return matrix [ currentCapacity ] [ item ]  ;
  }
  
  if(currentCapacity < weights[item])  {   // current item is greater than remaing capacity , skip this current item
   
   if(matrix[currentCapacity] [item + 1] == null)
    matrix[currentCapacity] [item + 1 ] = knapSack(currentCapacity, item+1) ;

   return matrix[currentCapacity] [item + 1 ] ;
  }
  else
  {
   if(matrix[currentCapacity] [ item +1 ] == null)
    matrix [currentCapacity ] [ item + 1] =  knapSack(currentCapacity, item+1) ;
   
   if(matrix [ currentCapacity - weights[item] ] [ item +1 ] == null)
    matrix [ currentCapacity - weights[item] ] [ item +1 ] = knapSack(currentCapacity - weights[item], item+1);

   return max(matrix [currentCapacity ] [ item + 1] , 
            values[item] + matrix [ currentCapacity - weights[item] ] [ item +1 ] ) ;
  }
 }
 
 /**
  * @return max value
  */
 private int max(int a , int b) {
  return a > b ? a : b ;
 }
}
//---------------------------------
class Helper {
 public static void main(String[] args) {
 
  int[] values={15,10,9,5};
  int[] weights={1,5,3,4,};
  int capacity=8;
  //  ans: 29 
 
       //int[] values={1,6,18,22,28};
       //int[] weights={1,2,5,6,7};
       //int capacity=5;
    //ans: 18 
  
  KnapSack2 knapsack =new KnapSack2(values, weights, capacity);
  System.out.println(knapsack.knapSack(capacity, 0));
 }
}

Time Complexity : O(nW) Space Complexity : O(nW)
Applications :
1.  Resource Allocation with financial constraints
2. Construction and scoring of heterogeneous test.
3. Selection of capital investment.

A more elegant recursive Code

References : http://www.slideshare.net/JennyGalino/knapsack-problem-11648128

Posted by @
Labels: ,

1 comment:

Subscribe to: Post Comments (Atom)