Knapsack Problem using Backtracking

Knapsack Problem using Backtracking can be solved as follow:

  • The knapsack problem is useful in solving resource allocation problems.
  • Let X = <x1, x2, x3, . . . . . , xn> be the set of n items,
    W = <w1, w2, w3, . . . , wn> and V = <v1, v2, v3, . . . , vn> be the set of weight and value associated with each item in X, respectively.
  • Let M be the total capacity of the knapsack, i.e. knapsack cannot hold items having a collective weight greater than M.
  • Select items from X such that it maximizes the profit and the collective weight of selected items does not exceed the knapsack capacity.
  • The knapsack problem has two variants. 0/1 knapsack does not allow breaking up the item, whereas a fractional knapsack does. 0/1 knapsack is also known as a binary knapsack.
  • The Knapsack problem can be formulated as,

Maximize sum_{i=1}^{n}v_i x_i subjected to sum_{i=1}^{n}w_i x_i le M

x_i in (0, 1) for binary knapsack

x_i in { 0, 1 } for fractional knapsack

Algorithm for Knapsack Problem using Backtracking

The algorithm for binary knapsack using a backtracking approach is described below:

Algorithm

 BK_KNAPSACK(M, W, V, fw, fp, X)
// Description : Solve knapsack problem using backtracking
// Input :
M: Knapsack capacity
W(1...n): Set of weight of the items
V(1...n): Set of profits associated with items
Fw: Final knapsack weight
Fp: Final earned profit
X(1...n): Solution vector
N: Total number of items

// Output : Solution tuple X, earned profit fp

// Initialization
cw ← 0		// Current weight
cp ← 0		// Current profit
fp ← – 1 
k ← 1		// Index of item being processed


loop:


while

(k ≤ n) AND (cw + W[k] ≤ M) 

do

	// Select kth item
  cw ← cw + W[k]
  cp ← cp + V[k]
  Y[k] ← 1
  k ← k + 1

end



if

 k > n 

then


  fp ← cp
  fw ← cw
  k ← n
  X ← Y

else


  Y[k] ← 0   // weight exceed knapsack capacity so skip item

end




while

BOUND(cp, cw, k) ≤ fp 

do


  

while

 k ≠ 0 AND Y[k] ≠ 1 

do


    k ← k – 1 			
  

end


  

if

 k == 0 

then

			
    

return

 
  

end


  Y[k] ← 0
  cw ← cw – W[k]			
  cp ← cp – P[k]

end


k ← k + 1

end loop

Algorithm for BOUND is described here:

Function

BOUND(cp, cw, k)
b ← cp
c ← cw

for

 i ← k + 1 to n 

do


  c ← c + W[i]
  

if

 c < M 

then


    b ← b + P[i]
  

else


    

return

 (b + (1 – (c – M)/W[i] * P[i])
  

end


end


return

 (b)

Examples

Example: Consider knapsack problem : n = 8. (W1, W2, W3, W4, W5, W6, W2, W8) = (1, 11, 21, 23, 33, 43, 45, 55), P = (11, 21, 31, 33, 43, 53, 55, 65), m = 110. Solve the problem using backtracking approach.

Solution:

Let arrange all items in non-decreasing order of p[i] / w[i].

i p[i] w[i] p[i]/w[i]
1 11 1 11
2 21 11 1.90
3 31 21 1.47
4 33 23 1.43
5 43 33 1.30
6 54 43 1.23
7 55 45 1.22
8 65 55 1.18

Here M = 110 and n = 8.

Initially,  cp = cw = 0, fp = – 1, k = 0

For k = 1:

cp    =   cp + p1 = 0 + 11 = 11

cw    =   cw + w1 = 0 + 1 = 1

cw    <   M, so select item 1

k    =   k + 1 = 2

For k=1:

cp    =   cp + p2 = 11 + 21 = 32

cw    =   cw + w2 = 1 + 11 = 12

cw    <   M, so select item 2

k    =   k + 1 = 2

For k = 2:

cp    =   cp + p3 = 32 + 31 = 63

cw    =   cw + w3 = 12 + 21 = 33

cw    <   M, so select item 3

k    =   k + 1 = 3

For k = 3:

cp    =   cp + p4 = 63 + 33 = 96

cw    =   cw + w4 = 33 + 23 = 56

cw    <   M, so select item 4

k    =   k + 1 = 4

For k = 4:

cp    =   cp + p5 = 96 + 43 = 139

cw    =   cw + w5 = 56 + 33 = 89

cw    <   M, so select item 5

k    =   k + 1 = 5

For k = 5:

cp    =   cp + p6 = 139 + 53 = 192

cw    =   cw + w6 = 89 + 43 = 132

cw    >   M, so reject item 6 and find upper bound

cp    =   cp – p6 = 192 – 53 = 139

cw    =   cw – w6 = 132 – 43 = 89

ub    =   cp + ((M – cw ) / w i+1) * pi+1

b    =   cp + [(110 – 89) / 43] * 53 = 164.88

Inclusion of any item from {I6, I7, I8} will exceed the capacity. So let’s backtrack to item 4.

The space tree would look like as shown in Fig. P. 6.7.2.

Upper bound at node 1:

ub    =   cp + ((M – cw ) / w i+1) * pi+1

=   139 + [(110 – 89)] / 43 * 53 = 164.88

Upper bound at node 2:

=   96 + [(110 – 56) / 33] * 43 = 166.09

Upper bound at node 3:

= 63 + [(110 – 33) / 33] * 43 = 163.33

Knapsack Problem using Backtracking example

Backtracking is useful in solving the following problems:


Additional Reading: Read More

You may also like...

Leave a Reply

Your email address will not be published.