Sırt Çantası Problemi

Problem Çözme Kalıpları konusu sekiz kalıbı ön koşuluyla birlikte ölçtü. Orada problemin adı kalıbın adıydı: iki işaretçi, kayan pencere, ızgara gezinmesi. Bu konu tersine döner. Adı kalıptan değil problemden gelen altı klasik problem ele alınır ve her birinde soru şudur: bu problem hangi kalıba oturuyor, ve oturduğu sanılan kalıp nerede kırılıyor.

İlk problem sırt çantasıdır ve iki yüzü vardır. Ağırlığı ve değeri olan eşyalar, sınırlı kapasiteli bir çanta. Bölünebilir varyantta bir eşyanın parçası alınabilir; 0/1 varyantında eşya ya bütün olarak alınır ya da hiç alınmaz. Tek bir kelimelik bu fark, aynı açgözlü sıranın bir varyantta kâhinle her girdide aynı yanıtı vermesine, ötekinde yanılmasına yol açar.

• KP1. Ortak tanımın üreteci ve dağarcığı aynen kullanılır: tohum 20260218, ikinci dağarcık 20260219, 40 dizi ve dizi başına 12 değer.
• KP2. Her dizinin ilk altı değeri ağırlık, son altı değeri değerdir. İkisinde de mutlak değer alınıp bir eklenir, böylece ağırlık ve değer 1 ile 21 arasında kalır.
• KP3. Kapasite toplam ağırlığın yarısının aşağı yuvarlanmışıdır. Girdiden türetilir, elle seçilmez; yoksa kapasiteyi seçerek istenen sonuç üretilebilirdi.
• KP4. Kâhin iki varyantta da kaba kuvvettir: bölünebilirde bütün doldurma sıraları, 0/1’de bütün 64 alt küme. Kâhin pahalıdır ve öyle kalır.
• KP5. Ölçü adımdır; süre ölçülmez. Adım, kâhin ile kalıbın karşılaştırılabilir tek birimidir.
• KP6. Ayrılan girdi sayısı 40 üzerindendir. Ortak tanımın Bölüm 5 çözünürlüğü gereği 3’ün altındaki fark ölçülmemiş sayılır.
• KP7. Açgözlü sıra iki varyantta da aynıdır: değer bölü ağırlık oranı azalan sıra. Değişen tek şey eşyanın bölünüp bölünemediğidir.
• KP8. Dinamik programlama yordamı Algoritma Tasarım Yaklaşımları konusunda kuruldu; tekrarlanmaz, yalnız kâhinle karşılaştırılır.
• KP9. Kapasite bir ayar olarak ayrıca süpürülür. Tek bir kapasitede ölçülüp genellenen bir ayrılma sayısı, seçilen ayarın sonucudur ve öyle yazılır.

Bölünebilir Varyant ve Kâhini

Bölünebilir varyantta bir eşyanın istenen kesri alınabilir. Sezgi açıktır: birim ağırlık başına en çok değer veren eşyadan başlanır, çanta dolana kadar sırayla devam edilir, son eşyadan kalan boşluk kadar kesir alınır.

Bu sezginin doğru olduğu iddia edilmez, sınanır. Kâhin, altı eşyanın bütün doldurma sıralarını dener ve en iyisini alır. Bir doldurma sırası çantayı sırayla doldurur; hangi sıra alınırsa alınsın elde edilen değer olabilecek en iyi değeri geçemez, ve en iyi değeri veren sıra bu 720 sıranın içindedir. Yani kâhin gerçekten bir üst sınırdır.

from itertools import permutations

TOHUM = 20260218


def uretec(tohum):
    d = tohum

    def sonraki(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return sonraki


def dagarcik(tohum=TOHUM, n=40, uzunluk=12):
    r = uretec(tohum)
    return [{"no": i + 1, "dizi": [r(30) - 9 for _ in range(uzunluk)]}
            for i in range(n)]


def esyalar(dizi):
    """Ortak tanimin 12 degerinden alti esya: agirlik ilk alti, deger son alti."""
    return [(abs(dizi[i]) + 1, abs(dizi[i + 6]) + 1) for i in range(6)]


class Sayac:
    def __init__(self):
        self.adim = 0

    def say(self):
        self.adim += 1


def kahin_bolunebilir(es, kap, s):
    """Butun doldurma siralari denenir, en iyisi alinir."""
    en = 0.0
    for p in permutations(range(len(es))):
        kalan, d = kap, 0.0
        for i in p:
            s.say()
            a, v = es[i]
            if a <= kalan:
                kalan, d = kalan - a, d + v
            else:
                d += v * kalan / a
                break
        en = max(en, d)
    return round(en, 4)


def kalip_bolunebilir(es, kap, s):
    """ONKOSUL: esya bolunebilir olmali. Deger/agirlik oranina gore acgozlu."""
    kalan, d = kap, 0.0
    for a, v in sorted(es, key=lambda t: -t[1] / t[0]):
        s.say()
        if a <= kalan:
            kalan, d = kalan - a, d + v
        else:
            d += v * kalan / a
            break
    return round(d, 4)


ayrilan, ak, ah = 0, 0, 0
for k in dagarcik():
    es = esyalar(k["dizi"])
    kap = sum(a for a, _ in es) // 2
    s1, s2 = Sayac(), Sayac()
    if kalip_bolunebilir(es, kap, s1) != kahin_bolunebilir(es, kap, s2):
        ayrilan += 1
    ak, ah = ak + s1.adim, ah + s2.adim
print("ilk ornek (agirlik, deger):", esyalar(dagarcik()[0]["dizi"]))
print("bolunebilir | girdi 40 | ayrilan", ayrilan, "| kalip adim", ak,
      "| kahin adim", ah, "| oran", round(ah / ak, 1))

ilk ornek (agirlik, deger): [(9, 5), (6, 2), (3, 17), (2, 18), (3, 7), (6, 2)]
bolunebilir | girdi 40 | ayrilan 0 | kalip adim 174 | kahin adim 100800 | oran 579.3

Üç sayı yan yana duruyor: kâhin 100.800 adım, kalıp 174 adım, ayrılan girdi 0. Kalıp 579,3 kat az adım harcıyor ve 40 girdinin 40’ında kâhinle aynı yanıtı veriyor.

Bölünebilirde açgözlünün yanılmamasının nedeni, kesir alma serbestliğinin bir değiş tokuş imkânı vermesidir. Çantada oranı düşük bir eşyadan bir birim ağırlık varsa, o birimi çıkarıp yerine oranı yüksek bir eşyadan bir birim koymak değeri düşürmez. Bu değiş tokuş akıl yürütmesi her zaman mümkün olduğu için, oran sırasından sapan hiçbir çözüm oran sırasını geçemez. Ön koşul tam olarak budur: birim ağırlık takas edilebilmeli.

Aynı Sıra, Bölünmeyen Eşya

0/1 varyantında bu takas ortadan kalkar. Bir birim ağırlık çıkarmak için eşyanın tamamını çıkarmak gerekir, ve yerine konan eşya da tam gelir. Açgözlü sıra değişmez, kod neredeyse aynıdır, ama ön koşul artık yoktur.

TOHUM = 20260218


def uretec(tohum):
    d = tohum

    def sonraki(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return sonraki


def esya_dagarcigi(tohum=TOHUM, n=40):
    """Ortak tanimin dagarcigi: 40 dizi x 12 deger, her diziden alti esya."""
    r = uretec(tohum)
    kume = []
    for i in range(n):
        z = [r(30) - 9 for _ in range(12)]
        kume.append((i + 1, [(abs(z[j]) + 1, abs(z[j + 6]) + 1) for j in range(6)]))
    return kume


class Sayac:
    def __init__(self):
        self.adim = 0

    def say(self):
        self.adim += 1


def kahin_01(es, kap, s):
    """Alti esyanin butun 64 altkumesi denenir."""
    en = 0
    for maske in range(1 << len(es)):
        a = d = 0
        for i, (ai, vi) in enumerate(es):
            s.say()
            if maske >> i & 1:
                a, d = a + ai, d + vi
        if a <= kap and d > en:
            en = d
    return en


def kalip_01(es, kap, s):
    """Ayni acgozlu sira, ama esya bolunemiyor."""
    kalan, d = kap, 0
    for a, v in sorted(es, key=lambda t: -t[1] / t[0]):
        s.say()
        if a <= kalan:
            kalan, d = kalan - a, d + v
    return d


def dp_01(es, kap, s):
    en = [0] * (kap + 1)
    for a, v in es:
        for c in range(kap, a - 1, -1):
            s.say()
            en[c] = max(en[c], en[c - a] + v)
    return en[kap]


def olc(cozucu, tohum):
    ayrilan, ak, ah, kayip = [], 0, 0, 0
    for no, es in esya_dagarcigi(tohum):
        kap = sum(a for a, _ in es) // 2
        s1, s2 = Sayac(), Sayac()
        a, b = cozucu(es, kap, s1), kahin_01(es, kap, s2)
        ak, ah = ak + s1.adim, ah + s2.adim
        if a != b:
            ayrilan.append(no)
            kayip = max(kayip, b - a)
    return ayrilan, ak, ah, kayip


for ad, cozucu, tohum in (("acgozlu 20260218", kalip_01, 20260218),
                          ("acgozlu 20260219", kalip_01, 20260219),
                          ("dinamik 20260218", dp_01, 20260218)):
    ay, ak, ah, f = olc(cozucu, tohum)
    print(ad, "| ayrilan", len(ay), "/40", ay[:6], "| kalip adim", ak,
          "| kahin adim", ah, "| en buyuk kayip", f)

acgozlu 20260218 | ayrilan 5 /40 [4, 21, 22, 32, 40] | kalip adim 240 | kahin adim 15360 | en buyuk kayip 7
acgozlu 20260219 | ayrilan 6 /40 [8, 11, 20, 28, 36, 39] | kalip adim 240 | kahin adim 15360 | en buyuk kayip 3
dinamik 20260218 | ayrilan 0 /40 [] | kalip adim 4544 | kahin adim 15360 | en buyuk kayip 0

Ayrılan Girdilerin Okunması

Açgözlü 0/1’de 40 girdinin 5’inde kâhinden ayrılıyor. Ayrılma oranı 0,1250 ve çözünürlük sınırının (3 girdi) üzerinde, yani ölçülmüş sayılır. Ayrıldığı girdilerin numaraları belli: 4, 21, 22, 32 ve 40. En büyük kayıp 7 değer birimidir — çantanın taşıyabileceği en iyi değerden yedi birim aşağıda kalınıyor.

Bu kayıp çıktıya bakılarak fark edilemez. Açgözlü yine bir sayı döndürüyor, yine kapasiteyi aşmıyor, yine geçerli bir seçim üretiyor. Geçerli olmak en iyi olmak demek değildir, ve aradaki farkı ancak kâhin gösterir. Kalıbın verdiği yanıtı tek başına inceleyerek yanlış olduğunu söylemenin bir yolu yoktur.

İkinci dağarcık zorunludur ve burada da uygulanıyor: 20260219 tohumuyla ayrılan girdi 6, oran 0,1500. Beş ile altı arasındaki fark çözünürlüğün altındadır, ama iki oran da aynı büyüklük düzenindedir. Sonuç dağarcığa bağlı değildir: açgözlü 0/1 varyantında girdilerin yaklaşık yedide birinde yanılıyor.

Bir Ayrılan Girdinin İçi

Ayrılan girdi sayısı tek başına bir sayıdır; neyin bozulduğunu göstermez. Dördüncü girdi açılıp seçimler yan yana konduğunda mekanizma görünür hale gelir. Aynı blok ayrıca kapasiteyi bir ayar olarak süpürür.

TOHUM = 20260218


def uretec(tohum):
    d = tohum

    def sonraki(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return sonraki


def esya_dagarcigi(tohum=TOHUM, n=40):
    r = uretec(tohum)
    kume = []
    for i in range(n):
        z = [r(30) - 9 for _ in range(12)]
        kume.append((i + 1, [(abs(z[j]) + 1, abs(z[j + 6]) + 1) for j in range(6)]))
    return kume


def kahin_01(es, kap):
    en, sec = 0, ()
    for maske in range(1 << len(es)):
        a = d = 0
        for i, (ai, vi) in enumerate(es):
            if maske >> i & 1:
                a, d = a + ai, d + vi
        if a <= kap and d > en:
            en, sec = d, tuple(i for i in range(len(es)) if maske >> i & 1)
    return en, sec


def kalip_01(es, kap):
    kalan, d, sec = kap, 0, []
    for i in sorted(range(len(es)), key=lambda j: -es[j][1] / es[j][0]):
        a, v = es[i]
        if a <= kalan:
            kalan, d = kalan - a, d + v
            sec.append(i)
    return d, tuple(sorted(sec))


es = dict(esya_dagarcigi())[4]
kap = sum(a for a, _ in es) // 2
print("girdi 4 |", es, "| kapasite", kap)
print("  acgozlu:", kalip_01(es, kap), " kahin:", kahin_01(es, kap))
print("kapasite payi -> ayrilan girdi (40 uzerinden)")
for pay in (2, 3, 4, 5, 6):
    ayrilan = sum(1 for _, e in esya_dagarcigi()
                  if kalip_01(e, sum(a for a, _ in e) * pay // 8)[0]
                  != kahin_01(e, sum(a for a, _ in e) * pay // 8)[0])
    print(f"  {pay}/8 -> {ayrilan}")

girdi 4 | [(5, 21), (6, 8), (9, 5), (2, 4), (19, 13), (18, 16)] | kapasite 29
  acgozlu: (38, (0, 1, 2, 3))  kahin: (45, (0, 1, 5))
kapasite payi -> ayrilan girdi (40 uzerinden)
  2/8 -> 3
  3/8 -> 13
  4/8 -> 5
  5/8 -> 12
  6/8 -> 8

Açgözlü dört eşya alıyor ve 38 değer topluyor; kullandığı ağırlık 22 ve geriye 7 birim boş yer kalıyor. Kâhin üç eşya alıyor, kapasiteyi tam dolduruyor ve 45 değer topluyor. Farkın kaynağı, açgözlünün oranı yüksek küçük eşyaları erken alması ve ardından oranı düşük ama büyük olan altıncı eşyaya yer bırakmamasıdır. Altıncı eşyanın oranı 0,889 ile listenin dördüncüsüdür, ama tek başına 16 değer taşır. Açgözlü onu asla göremez, çünkü sırayı yalnız orana bakarak kurar ve geriye dönmez.

Kapasite süpürmesi ikinci ve daha rahatsız edici sonucu veriyor. Ayrılan girdi sayısı kapasiteyle birlikte düzenli değişmiyor: toplam ağırlığın sekizde ikisinde 3, sekizde üçünde 13, sekizde dördünde 5, sekizde beşinde 12, sekizde altısında 8. Kalıbın yanılma sayısı bir sabit değil, ayarın bir işlevidir. Ölçüm tek bir kapasitede yapılıp genellenseydi, sekizde ikilik ayarda çıkan 3 sonucu açgözlünün neredeyse hep doğru olduğu izlenimini verirdi; sekizde üçlük ayarda çıkan 13 ise tam tersini söylerdi. Ölçünün hangi ayarda alındığı yazılmadıkça sayı okunamaz.

Dinamik Programlamanın Bedeli

Üçüncü satır dinamik programlamayı gösteriyor: 40 girdinin 40’ında kâhinle aynı yanıt, 4544 adım. Kâhin 15.360 adım harcıyor, yani doğru yanıt kaba kuvvetin 3,4’te biri kadar adımla alınabiliyor. Ama açgözlünün 240 adımıyla karşılaştırıldığında 18,9 kat pahalı.

Bu üç satır kursun ölçü okumasının tam karşılığıdır. Açgözlü ucuzdur ve yanılır; dinamik programlama pahalıdır ve yanılmaz; kâhin en pahalısıdır ve yanılmadığı tanım gereği bilinir. Aradaki seçim bir hız tercihi değil, kaç girdide yanlış yanıta razı olunduğu sorusudur.

Dinamik programlamanın adım sayısının kapasiteyle birlikte büyüdüğüne dikkat edilmeli. Burada kapasiteler küçüktür, çünkü ağırlıklar 1 ile 21 arasındadır. Ağırlıklar bin katına çıkarılsa eşya sayısı hiç değişmeden dinamik programlamanın adımı da bin katına çıkardı; kaba kuvvetin adımı ise hiç değişmezdi, çünkü o yalnız alt küme sayısına bakar. Hangi yordamın pahalı olduğu, girdinin hangi boyutunun büyüdüğüne bağlıdır.

Özet

• Sırt çantasının iki varyantı aynı açgözlü sırayı paylaşır; ayrıldıkları tek nokta eşyanın bölünüp bölünemediğidir, ve bu tek nokta yanıtı değiştirir.
• Bölünebilir varyantta açgözlü, 40 girdinin 40’ında kâhinle aynı yanıtı 174 adımda veriyor; kâhin aynı işi 100.800 adımda yapıyor.
• 0/1 varyantında aynı sıra 40 girdinin 5’inde kâhinden ayrılıyor ve en büyük kayıp 7 değer birimidir; ikinci dağarcıkta ayrılan girdi 6, oran aynı büyüklük düzeninde.
• Açgözlünün ürettiği yanıt her zaman geçerlidir; geçerli olması en iyi olduğu anlamına gelmez ve farkı yalnız kâhin gösterir.
• Kapasite bir ayar olarak süpürüldüğünde ayrılan girdi 3 ile 13 arasında oynuyor; kalıbın yanılma sayısı bir sabit değil, ayarın işlevidir.
• Dinamik programlama 40/40 doğru yanıtı 4544 adımda veriyor: kâhinden 3,4 kat ucuz, açgözlüden 18,9 kat pahalı.

Sonraki Adım

Sırt çantasında kaba kuvvet kâhini 64 alt küme taradı ve bu tarama küçük kaldı. Sonraki ders gezgin satıcı problemini alır; orada aday çözüm sayısı alt küme değil sıralama sayısıdır ve altı şehirden on şehre çıkıldığında tarama alanı sayıyla gösterilebilir biçimde patlar. Soru şu olacak: kâhin artık koşturulamayacak kadar büyüdüğünde, bir yaklaşık çözümün kâhinden yüzde kaç saptığı nasıl ölçülür.