Module 1 — Coin change: Greedy vs DP
Chọn hệ tiền và số tiền cần đổi. Greedy luôn lấy đồng lớn nhất; DP thử mọi đồng. Nếu greedy ra nhiều đồng hơn DP → greedy SAI, panel của nó bị tô đỏ.
Greedy
Luôn lấy đồng lớn nhất ≤ phần còn lại.
Dynamic Programming luôn đúng
dp[x] = 1 + min(dp[x − coin]), thử mọi coin.
Module 2 — Flowchart quyết định: Greedy hay DP?
Trả lời lần lượt các câu hỏi về bài toán của bạn. Flowchart sẽ dẫn tới kết luận Greedy hoặc DP.
Module 3 — 0/1 vs Fractional Knapsack (cùng input)
Cùng 3 món và cùng greedy theo mật độ v/w. Khác biệt duy nhất: 0/1 phải lấy nguyên cả món, fractional được cắt phần. Xem vì sao cùng chiến lược lại đúng/sai khác nhau.
Món cố định: A(w=10, v=60) · B(w=20, v=100) · C(w=30, v=120). Mật độ v/w: A=6.0, B=5.0, C=4.0.