0/1 Knapsack — Tối ưu hóa lựa chọn với ràng buộc

Mỗi sprint planning, team lead phải quyết định: với 40 story points capacity, chọn feature nào để maximize business value? Mỗi feature có effort (weight) và impact (value) khác nhau, không thể làm "nửa feature". Đây chính xác là bài toán 0/1 Knapsack — và nó xuất hiện trong mọi hệ thống phân bổ tài nguyên từ cloud computing đến logistics.

Amazon dùng Knapsack variants để tối ưu container loading. Netflix dùng nó cho bandwidth allocation giữa các streams. Khi bạn hiểu Knapsack, bạn hiểu nền tảng của mọi bài toán "chọn tối ưu dưới ràng buộc" — pattern phổ biến nhất trong cả interview lẫn production.

Bài toán: cho N items, mỗi item có weight và value. Túi chứa tối đa W đơn vị trọng lượng. Chọn items sao cho tổng value lớn nhất mà tổng weight không vượt quá W. Mỗi item chỉ được chọn hoặc không (0/1).

Bức tranh tư duy

Tưởng tượng bạn đang đóng hàng vào xe tải giao hàng ở Sài Gòn. Xe chỉ chở được 500kg. Trước mặt là 20 kiện hàng, mỗi kiện có trọng lượng và giá trị khác nhau. Bạn không thể chia nhỏ kiện hàng — lấy nguyên hoặc bỏ lại. Phải chọn tổ hợp kiện hàng nào cho tổng giá trị cao nhất?

Với mỗi kiện hàng, bạn có đúng 2 lựa chọn: lấy hoặc không lấy. Đây là bản chất "0/1" — binary decision cho từng item.

State: dp[i][w] = max value khi xét i items đầu, capacity còn w

Transition: Với item thứ i (weight=wt[i], value=val[i]):
  Nếu wt[i] > w:  dp[i][w] = dp[i-1][w]           (không đủ chỗ)
  Ngược lại:       dp[i][w] = max(dp[i-1][w],       (bỏ qua item i)
                                   dp[i-1][w-wt[i]] + val[i])  (lấy item i)

Bảng DP cho items = [(wt=1,val=1), (wt=3,val=4), (wt=4,val=5), (wt=5,val=7)], W=7:

         Capacity w →
         0   1   2   3   4   5   6   7
       ┌───────────────────────────────┐
     0 │ 0   0   0   0   0   0   0   0 │  ← Không có item
     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: mỗi ô dp[i][w] = giá trị tối đa khi xét i items đầu với capacity w. Answer ở góc dưới-phải.

Cốt lõi kỹ thuật

2D Bottom-Up — O(N×W) time, O(N×W) space

C++PythonJavaGo

cpp

int knapsack(vector<int>& wt, vector<int>& val, int W) {
    int n = wt.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (wt[i-1] > w) {
                dp[i][w] = dp[i-1][w];
            } else {
                dp[i][w] = max(dp[i-1][w],
                               dp[i-1][w - wt[i-1]] + val[i-1]);
            }
        }
    }
    return dp[n][W];
}

python

def knapsack(wt: list[int], val: list[int], W: int) -> int:
    n = len(wt)
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(W + 1):
            if wt[i-1] > w:
                dp[i][w] = dp[i-1][w]
            else:
                dp[i][w] = max(dp[i-1][w],
                               dp[i-1][w - wt[i-1]] + val[i-1])
    return dp[n][W]

java

public int knapsack(int[] wt, int[] val, int W) {
    int n = wt.length;
    int[][] dp = new int[n + 1][W + 1];

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (wt[i-1] > w) {
                dp[i][w] = dp[i-1][w];
            } else {
                dp[i][w] = Math.max(dp[i-1][w],
                                     dp[i-1][w - wt[i-1]] + val[i-1]);
            }
        }
    }
    return dp[n][W];
}

func knapsack(wt, val []int, W int) int {
    n := len(wt)
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, W+1)
    }

    for i := 1; i <= n; i++ {
        for w := 0; w <= W; w++ {
            if wt[i-1] > w {
                dp[i][w] = dp[i-1][w]
            } else {
                dp[i][w] = max(dp[i-1][w],
                               dp[i-1][w-wt[i-1]]+val[i-1])
            }
        }
    }
    return dp[n][W]
}

1D Space-Optimized — O(N×W) time, O(W) space ✅

Nhận xét quan trọng: dp[i][w] chỉ phụ thuộc vào hàng dp[i-1]. Ta giảm từ 2D xuống 1D bằng cách duyệt ngược w.

C++PythonJavaGo

cpp

int knapsackOptimized(vector<int>& wt, vector<int>& val, int W) {
    int n = wt.size();
    vector<int> dp(W + 1, 0);

    for (int i = 0; i < n; i++) {
        // CRITICAL: Duyệt ngược để mỗi item chỉ lấy 1 lần
        for (int w = W; w >= wt[i]; w--) {
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
        }
    }
    return dp[W];
}

python

def knapsack_optimized(wt: list[int], val: list[int], W: int) -> int:
    dp = [0] * (W + 1)
    for i in range(len(wt)):
        # Duyệt ngược: đảm bảo mỗi item chỉ dùng 1 lần
        for w in range(W, wt[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i])
    return dp[W]

java

public int knapsackOptimized(int[] wt, int[] val, int W) {
    int[] dp = new int[W + 1];
    for (int i = 0; i < wt.length; i++) {
        for (int w = W; w >= wt[i]; w--) {
            dp[w] = Math.max(dp[w], dp[w - wt[i]] + val[i]);
        }
    }
    return dp[W];
}

func knapsackOptimized(wt, val []int, W int) int {
    dp := make([]int, W+1)
    for i := 0; i < len(wt); i++ {
        for w := W; w >= wt[i]; w-- {
            dp[w] = max(dp[w], dp[w-wt[i]]+val[i])
        }
    }
    return dp[W]
}

Unbounded Knapsack — Mỗi item lấy nhiều lần

Thay đổi duy nhất: duyệt xuôi thay vì duyệt ngược. Duyệt xuôi cho phép dp[w - wt[i]] đã bao gồm item i → item được lấy lại.

C++PythonJavaGo

cpp

int unboundedKnapsack(vector<int>& wt, vector<int>& val, int W) {
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < (int)wt.size(); i++) {
        for (int w = wt[i]; w <= W; w++) {  // Duyệt XUÔI
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
        }
    }
    return dp[W];
}

python

def unbounded_knapsack(wt: list[int], val: list[int], W: int) -> int:
    dp = [0] * (W + 1)
    for i in range(len(wt)):
        for w in range(wt[i], W + 1):  # Duyệt XUÔI → lấy nhiều lần
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i])
    return dp[W]

java

public int unboundedKnapsack(int[] wt, int[] val, int W) {
    int[] dp = new int[W + 1];
    for (int i = 0; i < wt.length; i++) {
        for (int w = wt[i]; w <= W; w++) {
            dp[w] = Math.max(dp[w], dp[w - wt[i]] + val[i]);
        }
    }
    return dp[W];
}

func unboundedKnapsack(wt, val []int, W int) int {
    dp := make([]int, W+1)
    for i := 0; i < len(wt); i++ {
        for w := wt[i]; w <= W; w++ {
            dp[w] = max(dp[w], dp[w-wt[i]]+val[i])
        }
    }
    return dp[W]
}

Thực chiến

Tình huống: Phân bổ tài nguyên server

Bối cảnh: DevOps team cần chọn services để deploy trên server có RAM giới hạn 4GB. Mỗi service có RAM requirement và priority score. Tìm tổ hợp services tối ưu nhất.

Mục tiêu: Maximize tổng priority score trong RAM constraint.

C++PythonJavaGo

cpp

#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct Service {
    string name;
    int ramMB;
    int priority;
};

pair<int, vector<string>> scheduleServices(
    vector<Service>& services, int ramLimit) {
    int n = services.size();
    vector<vector<int>> dp(n + 1, vector<int>(ramLimit + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= ramLimit; w++) {
            dp[i][w] = dp[i-1][w];
            if (services[i-1].ramMB <= w) {
                dp[i][w] = max(dp[i][w],
                    dp[i-1][w - services[i-1].ramMB] + services[i-1].priority);
            }
        }
    }

    // Traceback: tìm services đã chọn
    vector<string> selected;
    int w = ramLimit;
    for (int i = n; i > 0 && w > 0; i--) {
        if (dp[i][w] != dp[i-1][w]) {
            selected.push_back(services[i-1].name);
            w -= services[i-1].ramMB;
        }
    }
    return {dp[n][ramLimit], selected};
}

python

def schedule_services(services: list[dict], ram_limit: int) -> tuple[int, list[str]]:
    """
    Chọn services tối ưu trong RAM constraint.
    services: [{"name": "nginx", "ram": 100, "priority": 90}, ...]
    """
    n = len(services)
    rams = [s["ram"] for s in services]
    priorities = [s["priority"] for s in services]

    dp = [[0] * (ram_limit + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(ram_limit + 1):
            dp[i][w] = dp[i-1][w]
            if rams[i-1] <= w:
                dp[i][w] = max(dp[i][w],
                               dp[i-1][w - rams[i-1]] + priorities[i-1])

    # Traceback
    selected = []
    w = ram_limit
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i-1][w]:
            selected.append(services[i-1]["name"])
            w -= rams[i-1]

    return dp[n][ram_limit], selected[::-1]

java

public record ServiceResult(int totalPriority, List<String> selected) {}

public ServiceResult scheduleServices(
        String[] names, int[] rams, int[] priorities, int ramLimit) {
    int n = names.length;
    int[][] dp = new int[n + 1][ramLimit + 1];

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= ramLimit; w++) {
            dp[i][w] = dp[i-1][w];
            if (rams[i-1] <= w) {
                dp[i][w] = Math.max(dp[i][w],
                    dp[i-1][w - rams[i-1]] + priorities[i-1]);
            }
        }
    }

    List<String> selected = new ArrayList<>();
    int w = ramLimit;
    for (int i = n; i > 0 && w > 0; i--) {
        if (dp[i][w] != dp[i-1][w]) {
            selected.add(0, names[i-1]);
            w -= rams[i-1];
        }
    }
    return new ServiceResult(dp[n][ramLimit], selected);
}

type ServiceResult struct {
    TotalPriority int
    Selected      []string
}

func scheduleServices(names []string, rams, priorities []int, ramLimit int) ServiceResult {
    n := len(names)
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, ramLimit+1)
    }

    for i := 1; i <= n; i++ {
        for w := 0; w <= ramLimit; w++ {
            dp[i][w] = dp[i-1][w]
            if rams[i-1] <= w && dp[i-1][w-rams[i-1]]+priorities[i-1] > dp[i][w] {
                dp[i][w] = dp[i-1][w-rams[i-1]] + priorities[i-1]
            }
        }
    }

    var selected []string
    w := ramLimit
    for i := n; i > 0 && w > 0; i-- {
        if dp[i][w] != dp[i-1][w] {
            selected = append([]string{names[i-1]}, selected...)
            w -= rams[i-1]
        }
    }
    return ServiceResult{dp[n][ramLimit], selected}
}

Phân tích:

Dùng 2D table vì cần traceback (tìm items đã chọn)
Nếu chỉ cần tổng value → dùng 1D optimized
Trade-off: O(N×W) space cho khả năng truy vết

Sai lầm điển hình

❌ Sai lầm 1: Duyệt xuôi trong 0/1 Knapsack

Vấn đề: Duyệt w từ nhỏ đến lớn khiến mỗi item bị lấy nhiều lần.

python

# SAI: Item được lấy lặp lại
for i in range(n):
    for w in range(wt[i], W + 1):  # Duyệt XUÔI
        dp[w] = max(dp[w], dp[w - wt[i]] + val[i])
        # dp[w - wt[i]] đã cập nhật → item i lấy lần 2, 3...

Tại sao sai: Khi duyệt xuôi, dp[w - wt[i]] đã được cập nhật trong iteration hiện tại, nghĩa là item i đã "có mặt" trong đó. Kết quả: 0/1 Knapsack trở thành Unbounded Knapsack — sai hoàn toàn.

python

# ĐÚNG: Duyệt ngược cho 0/1 Knapsack
for i in range(n):
    for w in range(W, wt[i] - 1, -1):  # Duyệt NGƯỢC
        dp[w] = max(dp[w], dp[w - wt[i]] + val[i])

❌ Sai lầm 2: Nhầm Knapsack với Greedy

Vấn đề: Chọn item theo tỷ lệ value/weight cao nhất (greedy) không cho kết quả tối ưu.

python

# SAI: Greedy approach
items.sort(key=lambda x: x.value / x.weight, reverse=True)
total = 0
for item in items:
    if item.weight <= remaining:
        total += item.value
        remaining -= item.weight

Tại sao sai: Greedy chỉ đúng cho Fractional Knapsack (có thể lấy một phần). Với 0/1 Knapsack, greedy bỏ lỡ tổ hợp tốt hơn. Ví dụ: items [(wt=10, val=60), (wt=20, val=100), (wt=30, val=120)], W=50. Greedy chọn item 0+1 (val=160), nhưng tối ưu là item 1+2 (val=220).

python

# ĐÚNG: Dùng DP cho 0/1 Knapsack
dp = [0] * (W + 1)
for i in range(n):
    for w in range(W, wt[i] - 1, -1):
        dp[w] = max(dp[w], dp[w - wt[i]] + val[i])

❌ Sai lầm 3: Quên edge case W=0 hoặc N=0

Vấn đề: Không xử lý trường hợp capacity bằng 0 hoặc không có item.

python

# SAI: Không check edge cases
def knapsack(wt, val, W):
    dp = [[0] * (W + 1) for _ in range(len(wt) + 1)]
    # Nếu W=0 hoặc wt rỗng → vẫn chạy vòng lặp vô nghĩa

Tại sao sai: Trong production, input validation là bước đầu tiên. Thiếu nó dẫn đến kết quả sai hoặc crash khi nhận input bất thường.

python

# ĐÚNG: Validate input
def knapsack(wt, val, W):
    if not wt or W <= 0:
        return 0
    dp = [0] * (W + 1)
    for i in range(len(wt)):
        for w in range(W, wt[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i])
    return dp[W]

Under the Hood

Hiệu năng

Approach	Time	Space	Traceback	Ghi chú
Naive Recursion	O(2^n)	O(n)	Không	Chỉ giáo dục
Memoization	O(N×W)	O(N×W)	Không trực tiếp	Top-down
2D Tabulation	O(N×W)	O(N×W)	✅ Có	Cần khi tìm items
1D Optimized	O(N×W)	O(W)	❌ Không	Production (chỉ cần value)

Pseudo-Polynomial Complexity

Knapsack là bài toán NP-Complete. Complexity O(N×W) trông polynomial, nhưng W không phải kích thước input — W là giá trị input. Kích thước input để biểu diễn W là log₂(W) bits.

Nếu W = 10⁹ → bảng DP có 10⁹ ô → không khả thi
Giải pháp cho W lớn: Branch & Bound, FPTAS (Fully Polynomial-Time Approximation Scheme)

0/1 vs Unbounded — Chiều duyệt quyết định tất cả

0/1 Knapsack (mỗi item 1 lần):
  w: W → wt[i]  (ngược)
  dp[w - wt[i]] là giá trị CŨ (hàng i-1) → item chưa lấy

Unbounded Knapsack (lấy nhiều lần):
  w: wt[i] → W  (xuôi)
  dp[w - wt[i]] là giá trị MỚI (hàng i) → item có thể đã lấy

Trade-offs

Yếu tố	2D Table	1D Optimized
Memory	O(N×W) — tốn	O(W) — tiết kiệm
Traceback	✅ Tìm được items	❌ Chỉ có tổng value
Debug	Dễ visualize	Khó hơn
Production	Khi cần biết chọn gì	Khi chỉ cần tổng

Checklist ghi nhớ

✅ Checklist triển khai

Nhận diện bài toán

[ ] Đề bài có "maximize/minimize value with constraint" → Knapsack
[ ] Mỗi item chỉ lấy/không lấy → 0/1 Knapsack
[ ] Item lấy nhiều lần → Unbounded Knapsack
[ ] Tìm subset có tổng = target → Subset Sum (biến thể)

Xây dựng lời giải

[ ] Định nghĩa state: dp[i][w] = max value với i items, capacity w
[ ] Transition: max(skip, take) — không lấy vs lấy item i
[ ] Base case: dp[0][w] = 0 cho mọi w (0 items → 0 value)

Tối ưu hóa

[ ] 2D → 1D: dp[i] chỉ phụ thuộc hàng i-1
[ ] 0/1: duyệt ngược w (W → wt[i])
[ ] Unbounded: duyệt xuôi w (wt[i] → W)
[ ] Cần traceback → giữ 2D table

Biến thể quan trọng

[ ] Subset Sum: weight = value = nums[i], dp là boolean
[ ] Equal Partition: target = sum/2, áp dụng Subset Sum
[ ] Coin Change: Unbounded + đếm cách hoặc min coins

Bài tập luyện tập

Bài 1: 0/1 Knapsack cơ bản — Foundation

Đề bài: Cho weights = [2, 3, 4, 5], values = [3, 4, 5, 6], W = 8. Tìm max value.

🧠 Quiz

Câu hỏi kiểm tra: Max value đạt được là?

[ ] A. 9
[ ] B. 10
[x] C. 12
[ ] D. 18 Giải thích: Chọn items có weight 3 và 5 (tổng weight=8, tổng value=4+6=10)... thực tế chọn items weight 2+3+... Thử: item 0(w=2,v=3) + item 1(w=3,v=4) + item 3(w=5,v=6) → w=10>8. item 0+1+2 → w=9>8. item 0+1 → w=5,v=7. item 2+3 → w=9>8. item 1+3 → w=8,v=10. item 0+2 → w=6,v=8. item 0+1+gap → item 0+2=8,v=8. Best: item 0+1+2: w=2+3+4=9>8. item 0(2,3)+item 3(5,6)=w7,v9 vs item 1(3,4)+item 2(4,5)=w7,v9 vs item 1+3=w8,v10 vs item 0+1+... Chọn C=12 nếu items khác. Chọn tổ hợp {0,2,3}: w=2+4+5=11>8. {0,1}: w=5,v=7. {1,3}: w=8,v=10. Đáp án: dp tính được max=10. C sai, B đúng.

💡 Gợi ý

Viết bảng DP 2D, điền từng ô
Hoặc dùng 1D optimized với duyệt ngược
Traceback để tìm items đã chọn

✅ Lời giải

python

def solve():
    wt = [2, 3, 4, 5]
    val = [3, 4, 5, 6]
    W = 8
    dp = [0] * (W + 1)
    for i in range(len(wt)):
        for w in range(W, wt[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i])
    return dp[W]  # Output: 10

Phân tích: Time O(N×W) = O(4×8) = 32 operations. Space O(W) = O(8). Tổ hợp tối ưu: items index 1 và 3 (weight=3+5=8, value=4+6=10).

Bài 2: Subset Sum — Intermediate

Đề bài: Cho mảng nums = [3, 34, 4, 12, 5, 2], target = 9. Có subset nào có tổng bằng target không?

🧠 Quiz

Câu hỏi kiểm tra: Kết quả là?

[x] A. True (tồn tại subset)
[ ] B. False (không tồn tại)
[ ] C. Không xác định
[ ] D. Phụ thuộc thứ tự Giải thích: Subset {4, 5} có tổng 9 = target. Đáp án A. Subset Sum là biến thể Knapsack với weight = value = nums[i], dp là boolean.

💡 Gợi ý

Coi như 0/1 Knapsack: weight = value = nums[i], capacity = target
dp[t] = True nếu có subset tổng bằng t
Duyệt ngược giống 0/1 Knapsack

✅ Lời giải

python

def subset_sum(nums: list[int], target: int) -> bool:
    dp = [False] * (target + 1)
    dp[0] = True
    for num in nums:
        for t in range(target, num - 1, -1):
            dp[t] = dp[t] or dp[t - num]
    return dp[target]

print(subset_sum([3, 34, 4, 12, 5, 2], 9))  # True

Phân tích: Time O(N×target), Space O(target). Pattern: boolean DP — dp[t] |= dp[t - num].

Liên kết học tiếp

Từ khóa glossary: knapsack, balo, 0/1 knapsack, unbounded knapsack, subset sum, equal partition, resource allocation, NP-complete, pseudo-polynomial

Tìm kiếm liên quan: bài toán cái túi, tối ưu lựa chọn, phân bổ tài nguyên, DP 2 chiều, duyệt ngược

0/1 Knapsack — Tối ưu hóa lựa chọn với ràng buộc ​

Bức tranh tư duy ​

Cốt lõi kỹ thuật ​

2D Bottom-Up — O(N×W) time, O(N×W) space ​

1D Space-Optimized — O(N×W) time, O(W) space ✅ ​

Unbounded Knapsack — Mỗi item lấy nhiều lần ​

Thực chiến ​

Tình huống: Phân bổ tài nguyên server ​

Sai lầm điển hình ​

❌ Sai lầm 1: Duyệt xuôi trong 0/1 Knapsack ​

❌ Sai lầm 2: Nhầm Knapsack với Greedy ​

❌ Sai lầm 3: Quên edge case W=0 hoặc N=0 ​

Under the Hood ​

Hiệu năng ​

Pseudo-Polynomial Complexity ​

0/1 vs Unbounded — Chiều duyệt quyết định tất cả ​

Trade-offs ​

Checklist ghi nhớ ​

Bài tập luyện tập ​

Bài 1: 0/1 Knapsack cơ bản — Foundation ​

Bài 2: Subset Sum — Intermediate ​

Liên kết học tiếp ​

0/1 Knapsack — Tối ưu hóa lựa chọn với ràng buộc

Bức tranh tư duy

Cốt lõi kỹ thuật

2D Bottom-Up — O(N×W) time, O(N×W) space

1D Space-Optimized — O(N×W) time, O(W) space ✅

Unbounded Knapsack — Mỗi item lấy nhiều lần

Thực chiến

Tình huống: Phân bổ tài nguyên server

Sai lầm điển hình

❌ Sai lầm 1: Duyệt xuôi trong 0/1 Knapsack

❌ Sai lầm 2: Nhầm Knapsack với Greedy

❌ Sai lầm 3: Quên edge case W=0 hoặc N=0

Under the Hood

Hiệu năng

Pseudo-Polynomial Complexity

0/1 vs Unbounded — Chiều duyệt quyết định tất cả

Trade-offs

Checklist ghi nhớ

Bài tập luyện tập

Bài 1: 0/1 Knapsack cơ bản — Foundation

Bài 2: Subset Sum — Intermediate

Liên kết học tiếp