Lesson 19 — Greedy Fundamentals

3 module tương tác: (1) Fractional knapsack — sort theo ratio rồi lấy tham lam tới đầy; (2) Greedy đúng vs sai — coin change hệ {1,5,10,25} (đúng) vs {1,3,4} (sai); (3) Exchange argument — "đổi" một lời giải tối ưu thành greedy.

1. Fractional Knapsack — greedy theo ratio v/w

Ba lô sức chứa W = 50. Được lấy một phần của món → greedy lấy theo ratio = giá trị/khối lượng cao nhất. Bấm để chạy từng bước.

0 / 50 kg

Bấm "Sort theo ratio" để bắt đầu.

2. Greedy ĐÚNG vs SAI — coin change

So sánh greedy (lấy đồng lớn nhất) với lời giải tối ưu. Hệ canonical {1,5,10,25} → greedy đúng. Hệ {1,3,4} → greedy có thể sai.

Số tiền cần trả:

Greedy (đồng lớn nhất trước)

Tối ưu (DP)

3. Exchange Argument — nắn OPT thành Greedy

Activity selection: chọn nhiều hoạt động không chồng nhau nhất. Một lời giải tối ưu (xanh dương) có hoạt động đầu khác greedy. Ta "đổi" nó sang hoạt động greedy kết thúc sớm hơn (xanh lá) — vẫn hợp lệ, vẫn cùng số lượng → OPT không tệ đi.

Lời giải tối ưu ban đầu (xanh dương). Bấm "Bước đổi" để nắn về greedy.