Backtracking and 0/1 Knapsack Solution

What is Backtracking?

Backtracking is a systematic algorithmic technique that builds a solution incrementally, one component at a time, and abandons a partial candidate ("backtracks") as soon as it determines that this candidate cannot lead to a valid or optimal complete solution.

Key points:

• It explores a state-space tree of all possible states.
• At each node a decision is made (for knapsack: include or exclude an item).
• A bounding function prunes branches that cannot improve upon the best solution found so far.
• More efficient than brute force since unpromising subtrees are cut.

Backtracking Algorithm for 0/1 Knapsack

• Each item is either taken (1) or not (0), so the state-space tree is binary.
• Items are usually sorted by profit/weight ratio (descending) so the bound is tight.
• At each node compute an upper bound using the fractional knapsack relaxation on remaining items. If bound <= bestProfit, prune.

Algorithm BKnap(i, cw, cp):        // cw=current weight, cp=current profit
  if cw <= W and cp > maxProfit:
      maxProfit = cp
  if i > n: return
  if Bound(i, cw, cp) > maxProfit:
      // include item i
      BKnap(i+1, cw + w[i], cp + p[i])   // only if cw+w[i] <= W
  // exclude item i
  BKnap(i+1, cw, cp)

Numerical Solution

Given Data

Capacity $W = 10$ kg.

Sort by ratio (descending):

Bound formula

$$\text{Bound}=cp+\text{(fractional knapsack value of remaining items in remaining capacity)}$$

State-Space Tree (order 4,2,1,3)

Node 1 (root): $cw=0,\ cp=0$ Bound $=10+5+3+\tfrac{0}{4}\cdot6 = 18$ (after 4,2,1 weight $=10$, capacity full). So overall root bound $=18$.

Include Item 4: $cw=5,\ cp=10$

• Bound: add 2 ($p=5$) → cap 2 left, add 1 ($p=3$) → cap 0. Bound $=10+5+3=18$.

  Include Item 2: $cw=8,\ cp=15$

  • Bound $=15+3=18$ (item 1 fits, cap 2).

    Include Item 1: $cw=10,\ cp=18$ - feasible, cap $=0$. $$\boxed{maxProfit = 18,\quad {4,2,1}}$$

    Exclude Item 1: $cw=8,\ cp=15$, cap 2. Bound $=15+\tfrac{2}{4}\cdot6=18$. Item 3 (w=4) does not fit; best stays 15 < 18. Pruned / no improvement.

  Exclude Item 2: $cw=5,\ cp=10$, cap 5. Bound $=10+3+\tfrac{3}{4}\cdot6=17.5 < 18$. Pruned.

Exclude Item 4: $cw=0,\ cp=0$, cap 10. Bound $=5+3+6+\tfrac{2}{5}\cdot10$? Remaining items 2,1,3 total weight $=3+2+4=9\le10$, so all fit: profit $=5+3+6=14 < 18$. Pruned.

Verification (best combination)

Items 1, 2, 4: weight $=2+3+5=10 \le 10$, profit $=3+5+10=18$. ✔

Any other feasible set:

• ${2,3,1}$: w $=9$, p $=14$
• ${4,3}$: w $=9$, p $=16$
• ${4,2}$: w $=8$, p $=15$

Maximum is 18.

Final Answer

$$\textbf{Optimal profit} = 18,\qquad \textbf{Items selected} = {1,\ 2,\ 4}$$ with total weight $10$ kg exactly filling the knapsack.

Quick Sort - Trace, Best and Worst Complexity

STEP 1 - Given Data

• Array to sort: $A[] = {15, 7, 6, 23, 18, 34, 25}$, indices $0$ to $6$
• $n = 7$ elements
• Required: trace Quick Sort, and best and worst case time complexity
• Pivot rule not specified. I use the first element as pivot (standard TU convention, Lomuto/Hoare style).

STEP 2 - Solve

I use the Hoare-style partition with pivot = first element.

Initial: pivot = 15, range [0..6]

 15   7   6   23   18   34   25
  0   1   2    3    4    5    6

• $i$ from left moves right while $A[i] < 15$: $A[1]=7<15$, $A[2]=6<15$, $A[3]=23\ge15$ → stop at $i=3$.
• $j$ from right moves left while $A[j] > 15$: $A[6]=25>15$, $A[5]=34>15$, $A[4]=18>15$, $A[3]=23>15$, $A[2]=6\le15$ → stop at $j=2$.
• $i > j$, so swap pivot $A[0]$ with $A[j]=A[2]$:

$${6, 7, \mathbf{15}, 23, 18, 34, 25}$$

Pivot 15 now at index 2. Left part = ${6,7}$, right part = ${23,18,34,25}$.

Left sub-array {6, 7}, pivot = 6, range [0..1]

• $i$: $A[1]=7\ge6$ → stop at $i=1$.
• $j$: $A[1]=7>6$ → move to $j=0$.
• $i>j$, swap pivot $A[0]$ with $A[0]$ → no change.

$${\mathbf{6}, 7}$$

Pivot 6 at index 0; right part ${7}$ single element, sorted.

Right sub-array {23, 18, 34, 25}, pivot = 23, range [3..6]

 23   18   34   25
  3    4    5    6

• $i$: $A[4]=18<23$, $A[5]=34\ge23$ → stop at $i=5$.
• $j$: $A[6]=25>23$, $A[5]=34>23$, $A[4]=18\le23$ → stop at $j=4$.
• $i>j$, swap pivot $A[3]$ with $A[4]$:

$${18, \mathbf{23}, 34, 25}$$

Pivot 23 at index 4. Left part ${18}$ sorted; right part ${34,25}$.

Sub-array {34, 25}, pivot = 34, range [5..6]

• $i$: $A[6]=25<34$ → $i$ goes past range, stop at $i=6$ (or beyond).
• $j$: $A[6]=25\le34$ → stop at $j=6$.
• $i \ge j$, swap pivot $A[5]$ with $A[6]$:

$${25, \mathbf{34}}$$

Final Sorted Array

$$A[] = {6, 7, 15, 18, 23, 25, 34}$$

Time Complexity

Best Case: $O(n \log n)$

• Pivot splits the array into two nearly equal halves each time.
• Recurrence: $T(n) = 2T(n/2) + O(n)$
• Solution: $T(n) = O(n \log n)$

Worst Case: $O(n^2)$

• Pivot is always the smallest or largest element (e.g., an already sorted array).
• One partition has $n-1$ elements, the other $0$.
• Recurrence: $T(n) = T(n-1) + O(n)$
• Solution: $T(n) = O(n^2)$