Scribd
Upload
10 views3 pages

Activity

The document explains the 0/1 Knapsack problem using both Top-Down (Memoization) and Bottom-Up (Tabulation) approaches. It details the items, their values and weights, and the optimal selection of items B and C, which yield a total value of 18 and a total weight of 5. A step-by-step breakdown of the recursive function and dynamic programming table is provided to illustrate the solution process.

Uploaded by

muhamnadali044
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
10 views3 pages

Activity

The document explains the 0/1 Knapsack problem using both Top-Down (Memoization) and Bottom-Up (Tabulation) approaches. It details the items, their values and weights, and the optimal selection of items B and C, which yield a total value of 18 and a total weight of 5. A step-by-step breakdown of the recursive function and dynamic programming table is provided to illustrate the solution process.

Uploaded by

muhamnadali044
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Sure!

The image you provided represents a 0/1 Knapsack problem using a recursion tree,
which is a top-down approach with recursion + memoization. Let's represent both Top-Down
(Memoization) and Bottom-Up (Tabulation) approaches in table format, step by step.

� Problem Summary

 Items: A, B, C
 Values: A=1, B=7, C=11
 Weights: A=1, B=2, C=3
 Capacity: 5

🔼 Top-Down Approach (Memoization)


We define a recursive function:
knapsack(i, remaining_capacity) where i is the item index and remaining_capacity is
the current weight left.

Remaining Total Total


Step Item iIndex Decision Items Chosen
Capacity Value Weight
1 0 5 Try A (include) A 1 1
2 1 4 Try B (include) A, B 8 3
Try C (include) A, B, C
3 2 2 19 6 (exceeds)
❌ (invalid)
4 2 2 Skip C A, B 8 3
5 1 4 Skip B A 1 1
6 2 4 Try C (include) A, C 12 4
7 2 4 Skip C A 1 1
8 0 5 Skip A 0 0
9 1 5 Try B (include) B 7 2
Try C (include)
10 2 3 B, C 18 ✅ 5✅
✅
11 2 3 Skip C B 7 2
12 1 5 Skip B 0 0
13 2 5 Try C (include) C 11 3
14 2 5 Skip C 0 0

✅ Best: B and C with Value 18, Weight 5

🔽 Bottom-Up Approach (Tabulation)


Create a DP table dp[i][w] where i is the item index and w is the capacity from 0 to 5.

Step-by-step Table Build

Item Weight Value


A 1 1
B 2 7
C 3 11

Initialize:
dp[0][w] = 0 for all w (no items, zero value)

Build Table

i (Item Index) Capacity (w) = 0 1 2 3 4 5


0 (no item) 0 000 0 0
1 (A) 0 111 1 1
2 (B) 0 178 8 8
3 (C) 0 1 7 11 12 18 ✅

Explanation

 At i=1 (Item A), you can only put it in if w >= 1


 At i=2 (Item B), you can combine it with A or just take B if it has more value
 At i=3 (Item C), the max value at capacity 5 is 18, which is from choosing B and C

✅ Best: Value 18 at dp[3][5] — Items B and C

✅ Final Answer
 Optimal Selection: Items B and C
 Total Value: 18
 Total Weight: 5

You might also like