Explain 0/1 Knapsack Problem with example.


Question: Explain 0/1 Knapsack Problem with example.
  1. Knapsack problem is also called as rucksack problem.
  2. It is a problem in combinatorial optimization.
  3. Knapsack problem states that: Given a set of items, each with a mass and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
  4. There are two versions of the problem:
    a. 0/1 Knapsack Problem: Items are indivisible; you either take an item or not. Some special instances can be solved with dynamic programming.
    b. Fractional knapsack problem: Items are divisible; you can take any fraction of an item.
0/1 Knapsack Problem:
i. In 0/1 Knapsack problem, items can be entirely accepted or rejected.
ii. Given a knapsack with maximum capacity W, and a set S consisting of n items.
iii. Each item i has some weight wiand benefit value bi(all wiand W are integer values).
iv. The problem is how to pack the knapsack to achieve maximum total value of packed items.
v. For solving the knapsack problem we can generate the sequence of decisions in order to obtain the optimum selection.
vi. Let Xn be the optimum sequence and there are two instances {Xn} and {Xn-1, Xn-2… X1}.
vii. So from {Xn-1, Xn-2… X1} we will choose the optimum sequence with respect to Xn.
viii. The remaining set should fulfill the condition of filling Knapsack of capacity W with maximum profit.
ix. Thus, 0/1 Knapsack problem is solved using the principle of optimality
To solve this problem using dynamic programming method we will perform following steps:
Steps:
  1. Let, fi (yj)be the value of optimal solution.
  2. Using formula: fi(yj)=maxfi1(y),fi1(ywi)+pi to solve problem.
  3. Then Si is a pair (p, w) where p=f(yj)and w=yj
  4. Initially S0=(0,0)
  5. Then S1i=(P,W)|(Ppi,Wwi)Si
  6. S1i+1 can be computed by merging Si  and  S1i
  7. This is used for obtaining optimal solution.
Example: Solve knapsack instance M =8 and N = 4. Let Pi=  and  Wi are as shown below.
iPiWi
112
223
354
465
Solution:
Build sequence of decision S0,S1,S2.
Initially S0=(0,0)
S10=(1,2)
This means while building S01 we select the next ith pair. For S10 we have selected first (P, W) pair which is (1, 2).
NowS1=MergeS0andS10=(0,0),(1,2)S11={Select next pair (P, W) and add it with S1}=(2,3),(2+0,3+0),(2+1,3+2)=(2,3),(3,5)since Repetition of (2, 3) is avoided.
S2=MergeS1andS11=(0,0),(1,2),(2,3),(3,5)S21={Select next pair (P, W) and add it with S2}=(5,4),(6,6),(7,7),(8,9)
S3={Merge S2 and S21}S3=(0,0),(1,2),(2,3),(5,4),(6,6),(7,7),(8,9)
Note that the pair (3, 5) is purged from S3. This is because, let us assume (Pj,Wj)=(3,5)and(Pk,Wk)=(5,4), Here PjPk and Wj>Wk is true hence we will eliminate pair (Pj,Wj) i.e (3, 5) from S3
S13={Select next pair (P, W) and add it with S3}=(6,5),(7,7),(8,8),(11,9),(12,11),(13,12),(14,14)S4=(0,0),(1,2),(2,3),(5,4),(6,6),(7,7),(8,9),(6,5),(7,7),(8,8),(11,9),(12,11),(13,12),(14,14)
Now we are interested in M =8. We get pair (8, 8) in S4. Hence we will set X4=1. Now we select next object (PP4) and (WW4) i.e (8 - 6) and (8 - 5). i.e (2, 3) Pair (2, 3) € S2 hence set X2=1. So we get the final solution as (0, 1, 0, 1)


Post a Comment

Other post

Online paisa kamaye apne android mobile se

अगर आपके पास Android मोबाइल है तो आप कमा सकते हैं ,1500 से ₹2000 Daily Report Exclusive 9 November. 2017 02:01 अब हम घर बैठे आॅनलाइ...

[blogger]

MKRdezign

Contact Form

Name

Email *

Message *

Powered by Blogger.
Javascript DisablePlease Enable Javascript To See All Widget