Scribd
Upload
12 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 capacity, ultimately determining that the optimal selection is items B and C, yielding 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 DOCX, PDF, TXT or read online on Scribd
12 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 capacity, ultimately determining that the optimal selection is items B and C, yielding 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 DOCX, 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