Module greedy 

Ochko’z algoritmlar (Greedy)

Darslik: 09-greedy/

Ochko’z yondashuv: har qadamda “hozir eng yaxshi ko’ringan” variantni tanlaymiz va orqaga qaytmaymiz. Sodda va tez — lekin har doim ham to’g’ri emas.

Qachon ochko’zlik to’g’ri javob beradi?

Ikki shart bajarilishi kerak:

1. Greedy choice property — mahalliy eng yaxshi tanlov global yechimning bir qismi bo’la oladi;
2. Optimal substructure — masalaning optimal yechimi kichik qismlarning optimal yechimlaridan quriladi.

Ochko’zlik vs Dinamik dasturlash

	Greedy	DP
Tanlov	Bittasini olib, qaytmaydi	Hamma variantni ko’radi
Tezlik	Odatda O(n log n)	Odatda O(n·W) yoki ko’proq
Kafolat	Faqat shartlar bajarilsa	Har doim optimal

Klassik misol: bo’linadigan xalta masalasi (fractional knapsack) — ochko’zlik ishlaydi. Bo’linmaydigan 0/1 xalta — ochko’zlik xato qiladi, DP kerak (crate::dp::knapsack_01).

Structs

Activity

Tadbir: boshlanish va tugash vaqti.

Item

Xaltaga solinadigan buyum: qiymati va og’irligi.

Functions

activity_selection

Tadbirlarni tanlash: bitta zalda maksimal nechta tadbir o’tkazish mumkin?

coin_change_greedy

Qaytim berish (coin change) — ochko’z yondashuv.

fractional_knapsack

Bo’linadigan xalta masalasi (fractional knapsack).

huffman_codes

Huffman kodlari: har bir belgi uchun o’zgaruvchan uzunlikdagi ikkilik kod.

huffman_encoded_len

Matn Huffman bilan kodlanganda necha bit egallaydi.

min_platforms

Minimal perron soni: bir vaqtning o’zida stansiyada eng ko’pi bilan nechta poyezd turadi?