Ochko'z algoritmlar

def ochkoz_maydala(nominallar, summa):
    """Har safar eng katta tangani oladi. O(n log n)."""
    natija = []
    qolgan = summa

    for tanga in sorted(nominallar, reverse=True):
        soni = qolgan // tanga
        if soni:
            natija.extend([tanga] * soni)
            qolgan -= tanga * soni

    return natija if qolgan == 0 else None


nominallar = [1, 5, 10, 25, 50, 100]
for summa in [63, 87, 130]:
    tangalar = ochkoz_maydala(nominallar, summa)
    print(f"{summa:>4} so'm -> {len(tangalar)} ta tanga: {tangalar}")

def taqqosla(nominallar, summa):
    """Ochko'z va DP yechimlarini taqqoslaydi."""
    ochkoz = ochkoz_maydala(nominallar, summa)

    CHEKSIZ = float("inf")
    jadval = [0] + [CHEKSIZ] * summa
    for joriy in range(1, summa + 1):
        for tanga in nominallar:
            if tanga <= joriy:
                jadval[joriy] = min(jadval[joriy], jadval[joriy - tanga] + 1)

    optimal = jadval[summa]
    ochkoz_soni = len(ochkoz) if ochkoz else CHEKSIZ

    holat = "to'g'ri" if ochkoz_soni == optimal else "XATO"
    print(f"  Nominallar {nominallar}, summa {summa}")
    print(f"    Ochko'z: {ochkoz_soni} ta {ochkoz}")
    print(f"    Optimal: {optimal} ta")
    print(f"    Natija:  {holat}\n")


taqqosla([1, 5, 10, 25], 30)
taqqosla([1, 3, 4], 6)
taqqosla([1, 15, 25], 30)

def mashgulotlarni_rejalashtir(mashgulotlar):
    """Eng ko'p mashg'ulotni joylashtiradi. O(n log n)."""
    # Tugash vaqti bo'yicha saralaymiz - ochko'z tanlovning kaliti
    tartiblangan = sorted(mashgulotlar, key=lambda m: m[2])

    tanlangan = []
    oxirgi_tugash = 0

    for nomi, boshlanish, tugash in tartiblangan:
        if boshlanish >= oxirgi_tugash:
            tanlangan.append((nomi, boshlanish, tugash))
            oxirgi_tugash = tugash

    return tanlangan


mashgulotlar = [
    ("Python darsi",      9, 11),
    ("Algoritmlar",      10, 12),
    ("Ma'lumotlar bazasi", 11, 13),
    ("Veb dasturlash",   12, 14),
    ("Ingliz tili",      13, 15),
    ("Matematika",        9, 14),
]

tanlangan = mashgulotlarni_rejalashtir(mashgulotlar)

print(f"{'Mashg‘ulot':<22}{'Vaqt':>12}")
print("-" * 34)
for nomi, boshlanish, tugash in tanlangan:
    print(f"{nomi:<22}{boshlanish:>6}:00 - {tugash}:00")
print("-" * 34)
print(f"Jami {len(tanlangan)} ta mashg'ulot joylashtirildi "
      f"({len(mashgulotlar)} tadan)")

def fraksion_ryukzak(buyumlar, quvvat):
    """Buyumlarni bo'lish mumkin bo'lgan ryukzak. O(n log n)."""
    # Birlik og'irlik uchun qiymat bo'yicha saralaymiz
    tartiblangan = sorted(buyumlar, key=lambda b: b[2] / b[1], reverse=True)

    jami_qiymat = 0.0
    tanlangan = []
    qolgan = quvvat

    for nomi, ogirlik, qiymat in tartiblangan:
        if qolgan <= 0:
            break

        if ogirlik <= qolgan:
            tanlangan.append((nomi, ogirlik, qiymat, 100))
            jami_qiymat += qiymat
            qolgan -= ogirlik
        else:
            ulush = qolgan / ogirlik
            tanlangan.append((nomi, qolgan, qiymat * ulush, ulush * 100))
            jami_qiymat += qiymat * ulush
            qolgan = 0

    return jami_qiymat, tanlangan


mahsulotlar = [
    ("Zafaron",   2, 12000),
    ("Asal",      5,  8000),
    ("Yong'oq",   8,  6000),
    ("Un",       10,  2000),
]
QUVVAT = 12

qiymat, tanlangan = fraksion_ryukzak(mahsulotlar, QUVVAT)

print(f"{'Mahsulot':<12}{'Og‘irlik':>10}{'Ulush':>9}{'Qiymat':>11}")
print("-" * 42)
for nomi, ogirlik, narx, ulush in tanlangan:
    print(f"{nomi:<12}{ogirlik:>8} kg{ulush:>8.0f}%{narx:>11,.0f}")
print("-" * 42)
print(f"{'JAMI':<12}{QUVVAT:>8} kg{'':>9}{qiymat:>11,.0f}")

import heapq
from collections import Counter


class HuffmanTugun:
    def __init__(self, belgi, chastota, chap=None, ong=None):
        self.belgi = belgi
        self.chastota = chastota
        self.chap = chap
        self.ong = ong

    def __lt__(self, boshqa):
        return self.chastota < boshqa.chastota


def huffman_kodlari(matn):
    """Har bir belgi uchun optimal ikkilik kod hosil qiladi."""
    chastotalar = Counter(matn)

    if len(chastotalar) == 1:                    # maxsus holat
        return {next(iter(chastotalar)): "0"}

    uyum = [HuffmanTugun(belgi, soni) for belgi, soni in chastotalar.items()]
    heapq.heapify(uyum)

    # Har safar eng kam uchraydigan ikkitasini birlashtiramiz
    while len(uyum) > 1:
        birinchi = heapq.heappop(uyum)
        ikkinchi = heapq.heappop(uyum)
        yangi = HuffmanTugun(None, birinchi.chastota + ikkinchi.chastota,
                             birinchi, ikkinchi)
        heapq.heappush(uyum, yangi)

    # Daraxt bo'ylab yurib kodlarni yig'amiz
    kodlar = {}

    def yur(tugun, kod=""):
        if tugun is None:
            return
        if tugun.belgi is not None:
            kodlar[tugun.belgi] = kod or "0"
            return
        yur(tugun.chap, kod + "0")
        yur(tugun.ong, kod + "1")

    yur(uyum[0])
    return kodlar


matn = "dasturlash dasturlash algoritm"
kodlar = huffman_kodlari(matn)
chastotalar = Counter(matn)

print(f"{'Belgi':<8}{'Chastota':>10}{'Kod':>10}{'Bit':>6}")
print("-" * 34)
for belgi, kod in sorted(kodlar.items(), key=lambda j: -chastotalar[j[0]]):
    korinish = repr(belgi) if belgi == " " else belgi
    print(f"{korinish:<8}{chastotalar[belgi]:>10}{kod:>10}{len(kod):>6}")

oddiy_bitlar = len(matn) * 8
huffman_bitlar = sum(chastotalar[b] * len(k) for b, k in kodlar.items())

print("-" * 34)
print(f"Oddiy kodlash (8 bit):  {oddiy_bitlar:>6} bit")
print(f"Huffman kodlash:        {huffman_bitlar:>6} bit")
print(f"Siqilish darajasi:      {(1 - huffman_bitlar / oddiy_bitlar):>6.1%}")