--- title: 'Sırt Çantası Problemi' source: 'https://academia.sh/tr/kurslar/ileri-algoritmalar/sirt-cantasi-problemi' course: 'İleri Algoritmalar ve Problem Çözme' language: tr updated: '2026-08-17T18:07:23+00:00' license: 'CC BY-SA 4.0' --- # Sırt Çantası Problemi Aynı açgözlü sıranın iki varyantta iki farklı sonuç vermesi: bölünebilir sırt çantasında 40 girdinin 40'ında kâhinle aynı yanıt ve 579,3 kat az adım; 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 birimi. Dinamik programlama 40/40 kâhinle aynı yanıtı 4544 adımda veriyor, kâhin 15.360 adımda. İkinci dağarcıkta ayrılan girdi 6, yani oran aynı büyüklük düzeninde kalıyor. 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. ```python 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. ```python 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. ```python 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.