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. (W₁, W₂, W₃, W₄, W₅, W₆, W₂, W₈) = (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 + p₁ = 0 + 11 = 11

cw    =   cw + w₁ = 0 + 1 = 1

cw    <   M, so select item 1

k    =   k + 1 = 2

For k=1:

cp    =   cp + p₂ = 11 + 21 = 32

cw    =   cw + w₂ = 1 + 11 = 12

cw    <   M, so select item 2

k    =   k + 1 = 2

For k = 2:

cp    =   cp + p₃ = 32 + 31 = 63

cw    =   cw + w₃ = 12 + 21 = 33

cw    <   M, so select item 3

k    =   k + 1 = 3

For k = 3:

cp    =   cp + p₄ = 63 + 33 = 96

cw    =   cw + w₄ = 33 + 23 = 56

cw    <   M, so select item 4

k    =   k + 1 = 4

For k = 4:

cp    =   cp + p₅ = 96 + 43 = 139

cw    =   cw + w₅ = 56 + 33 = 89

cw    <   M, so select item 5

k    =   k + 1 = 5

For k = 5:

cp    =   cp + p₆ = 139 + 53 = 192

cw    =   cw + w₆ = 89 + 43 = 132

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

cp    =   cp – p₆ = 192 – 53 = 139

cw    =   cw – w₆ = 132 – 43 = 89

ub    =   cp + ((M – cw ) / w _i+1) * p_i+1

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

Inclusion of any item from {I₆, I₇, I₈} 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) * p_i+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

Popular problems solved using backtracking:

Backtracking is useful in solving the following problems:

• N-Queen problem
• Sum of subset problem
• Graph coloring problem
• Knapsack problem
• Hamiltonian cycle problem

---

Additional Reading: Read More