0/1 Knapsack Problem - The Resource Optimizer

"Mọi bài toán allocation trong real-world đều là biến thể của Knapsack." - HPN

Problem Statement

Bạn là một tên trộm (hoặc một DevOps engineer - cùng bản chất 😏). Bạn có một túi đựng với giới hạn dung lượng W. Trước mặt bạn là N items, mỗi item có weight và value.

Câu hỏi: Chọn items nào để tổng value tối đa, mà tổng weight không vượt quá W?

Items: [(weight=2, value=3), (weight=3, value=4), (weight=4, value=5), (weight=5, value=6)]
Capacity W = 5

Optimal: Chọn item 0 + item 1 → weight = 5, value = 7

📘 Tại sao gọi "0/1"?

Mỗi item chỉ có 2 trạng thái: Lấy (1) hoặc Không lấy (0). Không được lấy một phần (khác với Fractional Knapsack).

Real-World Applications

Domain	Bài toán	Mapping
DevOps	Chọn processes chạy trong RAM giới hạn	Weight = RAM, Value = Priority
Finance	Portfolio optimization	Weight = Investment, Value = Expected Return
Logistics	Container loading	Weight = Volume, Value = Profit
Cloud	VM selection trên limited budget	Weight = Cost, Value = Performance
Gaming	Inventory management	Weight = Slots, Value = Item stats

Phân Tích DP

Nhận diện DP patterns

Checklist	Có?	Giải thích
Overlapping Subproblems	✅	`knapsack(i, w)` được gọi nhiều lần
Optimal Substructure	✅	`max(lấy item i, không lấy item i)`
"Maximize/Minimize" signal	✅	"Maximum value"

State Definition

dp[i][w] = Maximum value có thể đạt được khi:
           - Xét i items đầu tiên (index 0 → i-1)
           - Capacity còn lại là w

Transition (Công thức chuyển trạng thái)

Với mỗi item thứ i (weight = wt[i], value = val[i]):

python

if wt[i] > w:
    # Không đủ chỗ → Không lấy
    dp[i][w] = dp[i-1][w]
else:
    # Có thể lấy hoặc không → Chọn cái tốt hơn
    dp[i][w] = max(
        dp[i-1][w],              # Không lấy item i
        dp[i-1][w - wt[i]] + val[i]  # Lấy item i
    )

2D DP Table Visualization

Items: [(wt=1, val=1), (wt=3, val=4), (wt=4, val=5), (wt=5, val=7)]
Capacity W = 7

         Capacity w →
         0   1   2   3   4   5   6   7
       ┌───────────────────────────────┐
     0 │ 0   0   0   0   0   0   0   0 │  ← No items
     1 │ 0   1   1   1   1   1   1   1 │  ← Item 0 (wt=1, val=1)
   i 2 │ 0   1   1   4   5   5   5   5 │  ← +Item 1 (wt=3, val=4)
   ↓ 3 │ 0   1   1   4   5   6   6   9 │  ← +Item 2 (wt=4, val=5)
     4 │ 0   1   1   4   5   7   8   9 │  ← +Item 3 (wt=5, val=7)
       └───────────────────────────────┘
                                    ↑
                             Answer = 9

💡 Đọc bảng như thế nào?

Di chuyển từ trái→phải, trên→dưới
Mỗi ô dp[i][w] = max value với i items đầu và capacity w
Answer ở góc dưới phải: dp[n][W]

Step-by-Step Implementation

Step 1: Recursive (Intuition) - O(2^N) ❌

python

def knapsack_naive(weights: list, values: list, W: int, n: int) -> int:
    """
    ❌ BRUTE FORCE - Chỉ để hiểu logic.
    Time: O(2^N) - Mỗi item có 2 choice
    Space: O(N) - Call stack
    """
    # Base case: Hết items hoặc hết capacity
    if n == 0 or W == 0:
        return 0
    
    # Nếu item hiện tại nặng hơn capacity còn lại → Skip
    if weights[n-1] > W:
        return knapsack_naive(weights, values, W, n-1)
    
    # Chọn max của: Lấy vs Không lấy
    take = values[n-1] + knapsack_naive(weights, values, W - weights[n-1], n-1)
    skip = knapsack_naive(weights, values, W, n-1)
    
    return max(take, skip)

Step 2: Top-Down Memoization - O(N×W) ✅

python

from functools import lru_cache

def knapsack_memo(weights: list, values: list, W: int) -> int:
    """
    ✅ MEMOIZATION - Cache subproblems.
    Time: O(N × W)
    Space: O(N × W)
    """
    n = len(weights)
    
    @lru_cache(maxsize=None)
    def dp(i: int, w: int) -> int:
        if i == 0 or w == 0:
            return 0
        
        if weights[i-1] > w:
            return dp(i-1, w)
        
        return max(
            dp(i-1, w),                          # Skip
            values[i-1] + dp(i-1, w - weights[i-1])  # Take
        )
    
    return dp(n, W)

Step 3: Bottom-Up Tabulation - O(N×W) ✅

python

def knapsack_tabulation(weights: list, values: list, W: int) -> int:
    """
    ✅ CLASSIC DP - Build table iteratively.
    Time: O(N × W)
    Space: O(N × W)
    """
    n = len(weights)
    
    # dp[i][w] = max value với i items đầu, capacity w
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(W + 1):
            if weights[i-1] > w:
                dp[i][w] = dp[i-1][w]  # Không đủ chỗ
            else:
                dp[i][w] = max(
                    dp[i-1][w],                              # Skip
                    values[i-1] + dp[i-1][w - weights[i-1]]  # Take
                )
    
    return dp[n][W]

Step 4: Space-Optimized - O(W) ✅✅

python

def knapsack_optimized(weights: list, values: list, W: int) -> int:
    """
    ✅✅ PRODUCTION-READY - 1D array optimization.
    Time: O(N × W)
    Space: O(W)
    
    Key insight: dp[i] chỉ phụ thuộc vào dp[i-1]
                 → Chỉ cần 1 row!
    
    ⚠️ CRITICAL: Duyệt W từ lớn→nhỏ để tránh overwrite!
    """
    n = len(weights)
    dp = [0] * (W + 1)
    
    for i in range(n):
        # Duyệt ngược để đảm bảo mỗi item chỉ lấy 1 lần
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w], values[i] + dp[w - weights[i]])
    
    return dp[W]

⚠️ CRITICAL: Tại sao duyệt ngược?

python

# ❌ SAI: Duyệt xuôi
for w in range(weights[i], W + 1):
    dp[w] = max(dp[w], values[i] + dp[w - weights[i]])
    # dp[w - weights[i]] đã bị UPDATE → Item i được lấy nhiều lần!

# ✅ ĐÚNG: Duyệt ngược
for w in range(W, weights[i] - 1, -1):
    dp[w] = max(dp[w], values[i] + dp[w - weights[i]])
    # dp[w - weights[i]] vẫn là giá trị cũ → Item i chỉ lấy 1 lần

Production Code (Full Version)

python

# HPN Engineering Standard
# Implementation: 0/1 Knapsack - All Approaches + Traceback

from functools import lru_cache
from typing import List, Tuple


# ============================================
# CORE IMPLEMENTATIONS
# ============================================

def knapsack_optimized(weights: List[int], values: List[int], W: int) -> int:
    """
    ✅✅ O(N×W) time, O(W) space - Production.
    Returns: Maximum value achievable.
    """
    dp = [0] * (W + 1)
    
    for i in range(len(weights)):
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w], values[i] + dp[w - weights[i]])
    
    return dp[W]


def knapsack_with_items(
    weights: List[int], 
    values: List[int], 
    W: int
) -> Tuple[int, List[int]]:
    """
    Returns: (max_value, list of item indices selected)
    
    Sử dụng bảng 2D để traceback items đã chọn.
    """
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    
    # Build table
    for i in range(1, n + 1):
        for w in range(W + 1):
            if weights[i-1] > w:
                dp[i][w] = dp[i-1][w]
            else:
                dp[i][w] = max(
                    dp[i-1][w],
                    values[i-1] + dp[i-1][w - weights[i-1]]
                )
    
    # Traceback: Tìm items đã chọn
    selected_items = []
    i, w = n, W
    
    while i > 0 and w > 0:
        if dp[i][w] != dp[i-1][w]:
            # Item i-1 được chọn
            selected_items.append(i - 1)
            w -= weights[i - 1]
        i -= 1
    
    selected_items.reverse()
    return dp[n][W], selected_items


# ============================================
# VARIANTS
# ============================================

def unbounded_knapsack(weights: List[int], values: List[int], W: int) -> int:
    """
    Variant: Unbounded Knapsack - Mỗi item có thể lấy NHIỀU LẦN.
    (Còn gọi là Complete Knapsack)
    
    Thay đổi: Duyệt W từ nhỏ→lớn (cho phép reuse item)
    """
    dp = [0] * (W + 1)
    
    for i in range(len(weights)):
        # Duyệt xuôi → Cho phép lấy item nhiều lần
        for w in range(weights[i], W + 1):
            dp[w] = max(dp[w], values[i] + dp[w - weights[i]])
    
    return dp[W]


def subset_sum(nums: List[int], target: int) -> bool:
    """
    Variant: Subset Sum - Có thể chọn subset có tổng = target?
    (Knapsack với weight = value = nums[i])
    
    Time: O(N × target)
    Space: O(target)
    """
    dp = [False] * (target + 1)
    dp[0] = True  # Empty subset = sum 0
    
    for num in nums:
        for t in range(target, num - 1, -1):
            dp[t] = dp[t] or dp[t - num]
    
    return dp[target]


def partition_equal_subset(nums: List[int]) -> bool:
    """
    Variant: Partition Equal Subset Sum (LeetCode 416)
    Chia array thành 2 subset có tổng bằng nhau?
    
    → Chính là tìm subset có sum = total // 2
    """
    total = sum(nums)
    
    # Tổng lẻ → Không thể chia đều
    if total % 2 != 0:
        return False
    
    return subset_sum(nums, total // 2)


# ============================================
# REAL-WORLD EXAMPLE: PROCESS SCHEDULER
# ============================================

def schedule_processes(
    processes: List[dict],
    ram_limit: int
) -> Tuple[int, List[str]]:
    """
    Scenario: Chọn processes để chạy trong RAM giới hạn.
    
    Args:
        processes: [{"name": "nginx", "ram": 100, "priority": 80}, ...]
        ram_limit: Maximum RAM available (MB)
    
    Returns:
        (total_priority, list of process names)
    """
    names = [p["name"] for p in processes]
    rams = [p["ram"] for p in processes]
    priorities = [p["priority"] for p in processes]
    
    max_priority, selected_indices = knapsack_with_items(rams, priorities, ram_limit)
    selected_processes = [names[i] for i in selected_indices]
    
    return max_priority, selected_processes


# ============================================
# USAGE EXAMPLE
# ============================================

if __name__ == "__main__":
    # Basic knapsack
    weights = [1, 3, 4, 5]
    values = [1, 4, 5, 7]
    W = 7
    
    print(f"=== 0/1 Knapsack (W={W}) ===")
    print(f"Items: {list(zip(weights, values))}")
    
    max_val = knapsack_optimized(weights, values, W)
    print(f"Max value: {max_val}")
    
    max_val, items = knapsack_with_items(weights, values, W)
    print(f"Selected items: {items} → value = {max_val}")
    
    # Real-world example
    print(f"\n=== Process Scheduler ===")
    processes = [
        {"name": "nginx", "ram": 100, "priority": 90},
        {"name": "postgres", "ram": 256, "priority": 85},
        {"name": "redis", "ram": 64, "priority": 70},
        {"name": "node-app", "ram": 128, "priority": 95},
        {"name": "worker", "ram": 96, "priority": 60},
    ]
    ram_limit = 400
    
    total, selected = schedule_processes(processes, ram_limit)
    print(f"RAM limit: {ram_limit}MB")
    print(f"Selected: {selected}")
    print(f"Total priority: {total}")
    
    # Subset sum
    print(f"\n=== Subset Sum ===")
    nums = [3, 34, 4, 12, 5, 2]
    target = 9
    print(f"Can make sum {target} from {nums}? {subset_sum(nums, target)}")
)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188

Complexity Analysis

Approach	Time	Space	Use Case
Naive Recursion	$O (2^{N})$	$O (N)$	Chỉ để học
Memoization	$O (N \times W)$	$O (N \times W)$	General
Tabulation	$O (N \times W)$	$O (N \times W)$	Cần traceback
1D Optimized	$O (N \times W)$	$O (W)$	Production

⚠️ Pseudo-Polynomial

Knapsack là NP-Complete. Complexity $O (N \times W)$ không phải polynomial của input size!

Nếu W rất lớn (ví dụ $10^{9}$ ), cần approach khác (Branch & Bound, approximation).

Interview Cheat Sheet

Variant	Key Difference	Loop Direction
0/1 Knapsack	Mỗi item lấy 1 lần	W → 0 (ngược)
Unbounded	Item lấy nhiều lần	0 → W (xuôi)
Subset Sum	weight = value	Same as 0/1
Partition	target = sum/2	Same as 0/1

💡 HPN's Rule

"Thấy 'maximize value with constraint' → Knapsack. Lấy 1 lần = duyệt ngược. Lấy nhiều = duyệt xuôi."

0/1 Knapsack Problem - The Resource Optimizer ​

Problem Statement ​

Real-World Applications ​

Phân Tích DP ​

Nhận diện DP patterns ​

State Definition ​

Transition (Công thức chuyển trạng thái) ​

2D DP Table Visualization ​

Step-by-Step Implementation ​

Step 1: Recursive (Intuition) - O(2^N) ❌ ​

Step 2: Top-Down Memoization - O(N×W) ✅ ​

Step 3: Bottom-Up Tabulation - O(N×W) ✅ ​

Step 4: Space-Optimized - O(W) ✅✅ ​

Production Code (Full Version) ​

Complexity Analysis ​

Interview Cheat Sheet ​

0/1 Knapsack Problem - The Resource Optimizer

Problem Statement

Real-World Applications

Phân Tích DP

Nhận diện DP patterns

State Definition

Transition (Công thức chuyển trạng thái)

2D DP Table Visualization

Step-by-Step Implementation

Step 1: Recursive (Intuition) - O(2^N) ❌

Step 2: Top-Down Memoization - O(N×W) ✅

Step 3: Bottom-Up Tabulation - O(N×W) ✅

Step 4: Space-Optimized - O(W) ✅✅

Production Code (Full Version)

Complexity Analysis

Interview Cheat Sheet