# 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].

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

Backtracking is useful in solving the following problems: