Problem Statement:
Find the maximum value for the given capacity of Knapsack.
Input vectors are :
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:
Solution of the given problem is in the figure given below using 2-D matrix
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
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
|
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
louboutin shoes
ReplyDeletehermes online
nike outlet
vans
adidas tubular
nike cortez
moncler jackets
moncler
christian louboutin outlet