rust_algorithms/greedy/mod.rs
1//! # Ochko'z algoritmlar (Greedy)
2//!
3//! Darslik: `09-greedy/`
4//!
5//! **Ochko'z yondashuv:** har qadamda "hozir eng yaxshi ko'ringan" variantni tanlaymiz
6//! va **orqaga qaytmaymiz**. Sodda va tez — lekin har doim ham to'g'ri emas.
7//!
8//! ## Qachon ochko'zlik to'g'ri javob beradi?
9//!
10//! Ikki shart bajarilishi kerak:
11//!
12//! 1. **Greedy choice property** — mahalliy eng yaxshi tanlov global yechimning
13//! bir qismi bo'la oladi;
14//! 2. **Optimal substructure** — masalaning optimal yechimi kichik qismlarning
15//! optimal yechimlaridan quriladi.
16//!
17//! ## Ochko'zlik vs Dinamik dasturlash
18//!
19//! | | Greedy | DP |
20//! |---|---|---|
21//! | Tanlov | Bittasini olib, qaytmaydi | Hamma variantni ko'radi |
22//! | Tezlik | Odatda O(n log n) | Odatda O(n·W) yoki ko'proq |
23//! | Kafolat | Faqat shartlar bajarilsa | Har doim optimal |
24//!
25//! **Klassik misol:** *bo'linadigan* xalta masalasi (fractional knapsack) —
26//! ochko'zlik ishlaydi. *Bo'linmaydigan* 0/1 xalta — ochko'zlik **xato** qiladi,
27//! DP kerak ([`crate::dp::knapsack_01`]).
28
29mod classic;
30mod huffman;
31
32pub use classic::{
33 activity_selection, coin_change_greedy, fractional_knapsack, min_platforms, Activity, Item,
34};
35pub use huffman::{huffman_codes, huffman_encoded_len};