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
Dynamic Programming luôn đúng
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.
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.
Thử: cùng input — Fractional cho phép cắt món nên greedy theo tỉ lệ v/w là tối ưu; 0/1 không cắt được → phải DP xét mọi tổ hợp.