28 Sept 2013

Bellman - Ford Algorithm

                                                  Bellman - Ford Algorithm


  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
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
import java.util.ArrayList;
import java.util.List;
/**
 * Edge of Graph
 * @author Prateek
 */
class Edge {
 int src;
 int dest;
 int weight;

 public Edge(int src,int dest,int weight) {
  this.src=src;
  this.dest=dest;
  this.weight=weight;
 }

 @Override
 public String toString() {
  return "Edge: "+src+ " - " + dest + " | " +"  Weight: "+ weight;
 }
}

/**
 * Bellman's Algorithm for Single Source Shortest Path
 * @author Prateek
 *
 */
 class BellmanFord {
 
 private static final int MAX_INF=999999;

 private int mNumVertices;   // Number of vertices in the graph
 private int mNumEdges;  // Number of edges in the graph
 
 // Input Edge List
 private List<Edge> mEdgeList;  

 public BellmanFord(int numVertices,int numEdges) {
  this.mNumVertices=numVertices;
  this.mNumEdges=numEdges;
  
  this.mEdgeList=new ArrayList<Edge>(numEdges);
 }
 
 private  boolean bellmanFord(int src)
 {
  // maintains the updated distance
  int[] dist=new int[mNumVertices];
  
  //Initialisation
  for(int i=0;i<mNumVertices ; i++) 
   dist[i] = MAX_INF;
  dist[src]=0;
  
  for(int i=0;i<= mNumVertices ; i++)
  {
   for(int j=0;j< mNumEdges ; j++) 
   {
    Edge edge=mEdgeList.get(j);
    int u=edge.src;
    int v=edge.dest;
    int weight=edge.weight;
    
    // Relaxing the edge
    if(dist[v] > dist[u]+weight)
     dist[v]=dist[u]+weight;
   }
  }
  
  //check for negative cycles, by inspecting the distance of all vertices
  // if we find any dist[v] greater distance than dist[u]+ weight, that means 
  // we have already cycled through some edge more than once
  for(int i=0 ;i< mNumEdges ;i++)
  {
   Edge edge=mEdgeList.get(i);
   int u=edge.src;
   int v=edge.dest;
   int weight=edge.weight;
   
   if(dist[u]+weight < dist[v])
   {
    System.out.println("Undefined Graph , Shortest path cant be calculated");
    return false;
   }
  }
   
  printShortestPath(src , dist);
  return true;
 }
 
 private void printShortestPath(int src , int[] dist) {
  for(int i=0;i<mNumVertices ;i++)
   System.out.println(src + " ---> " + i + "    "   +dist[i]);
 }
 
 public static void main(String[] args) {
  BellmanFord graph=new BellmanFord(5, 6);
  graph.helper();
  
 }
 
 public void helper() {
  
  mEdgeList.add(new Edge(0, 1, 2));
  mEdgeList.add(new Edge(0, 2, 4));
  
  mEdgeList.add(new Edge(1, 3, 2));
  mEdgeList.add(new Edge(1, 2, 1));
  
  mEdgeList.add(new Edge(2, 4, 4));
  
  mEdgeList.add(new Edge(3, 4, 2));
  
  int sourceVertex = 0;
  bellmanFord(sourceVertex);
 }
}


References: http://faculty.ycp.edu/~dbabcock/PastCourses/cs360/lecture/lecture21.html

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