0/1 Knapsack Problem
n öğeniz var. i. öğenin ağırlığı weights[i] ve değeri values[i] kadardır. Çantanız en fazla toplam capacity ağırlık taşıyabilir. Her öğeden yalnızca bir tane vardır ve öğeyi ya tamamen çantanıza koyarsınız ya da geride bırakırsınız. Çantanıza koyabileceğiniz en yüksek toplam değeri döndürün.
Fonksiyon
- weightsinteger-array
- her bir öğenin ağırlığı
- valuesinteger-array
- her bir öğenin değeri
- capacityinteger
- çantanın taşıyabileceği en fazla ağırlık
- Döndürürinteger
- kapasiteye sığan ağırlıklardaki öğelerin toplam değerinin en büyüğü
Kısıtlar
1 ≤ n ≤ 100, buradan = weights.length = values.length1 ≤ weights[i] ≤ 10001 ≤ values[i] ≤ 1041 ≤ capacity ≤ 1000
Örnekler
- Girdi
- weights = [4, 2, 3, 5]values = [10, 4, 7, 12]capacity = 7
- Çıktı
- 17
- Açıklama
- 0 ve 2 numaralı öğelerin ağırlıkları 4 + 3 = 7, değerleri ise 10 + 7 = 17'dir. Önce en değerli öğeyi (ağırlık 5, değer 12) çantaya koymak, yalnızca 1 numaralı öğeye yetecek kadar yer bırakır ve toplam değeri 16 olur.
- Girdi
- weights = [5, 4, 3]values = [10, 7, 6]capacity = 7
- Çıktı
- 13
- Açıklama
- 1. ve 2. öğeler 4 + 3 = 7 ağırlığındadır ve 7 + 6 = 13 değerindedir. 0. öğe, ağırlık birimi başına 2 kazandırır; herhangi bir öğe kadar kazandırır, ancak ondan sonra kalan 2 birim hiçbir şeyi sığdırmaz.
- Girdi
- weights = [6, 8]values = [5, 9]capacity = 5
- Çıktı
- 0
- Açıklama
- Her iki öğe de 5'ten daha ağırdır, bu yüzden hiçbir şey sığmaz ve boş çantanın değeri 0'dır.
Ek soru
Kapasitenin 10^9'a ulaşabildiğini, değerlerin toplamının ise en fazla 10^4 olduğunu varsayalım. Tabloyu neye göre indekslerdiniz?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
0. öğeden başlayarak öğelere sırayla karar verin. Onu çantanıza koysanız da dışarıda bıraksanız da, sonrasındaki öğelerle ilgili aynı soruyla karşılaşırsınız. Bu soruda hangi sayı değişir?
Buradan sonraki en iyi değer yalnızca iki sayıya bağlıdır: hangi öğeye baktığınız ve ne kadar yer kaldığı. 100 öğe ve 1000 kapasiteyle bu tür yaklaşık 10^5 ikili vardır; dolayısıyla her birini bir kez hesaplayıp saklayabilirsiniz.
Başlangıçta hepsi 0 olacak şekilde, 0'dan
capacity'ye kadar her kapasiteciçinbest[c]değerini tut. Ağırlığıwve değerivolan bir öğe için,cdeğerinicapacity'denw'ye doğru azaltarak ilerle vebest[c]ilebest[c-w] + vdeğerlerinden büyük olanı tut. Azalan yönde ilerlemek, öğenin iki kez paketlenmesini önler.
Çözüm
Açgözlü sıralamaların hiçbiri işe yaramaz: en değerli öğeyi ilk sıraya koymak, ilk örnekte 17 değil 16 değerini verir. i. öğeden itibaren elde edilebilecek en iyi değer yalnızca i'ye ve kalan kapasiteye bağlıdır; bu kapasite 1000'e kadar olan bir tam sayıdır. Her ikili için bir tablo hücresi kullanmak O(n × capacity) verir ve kapasiteleri azalan sırayla dolaşırsanız tek bir satır yeterlidir.
Her öğe için her iki seçeneği de dene
Doğru, ama en büyük testlerde bitmiyor
Sezgi
best(i, room), i öğesinden itibaren room birim boş alanla elde edilebilecek en yüksek toplam değer olsun; son öğeyi geçince değer 0'dır. i öğesini atlamak best(i+1, room) değerini verir. weights[i] ≤ room olduğunda öğeyi çantaya koymak values[i] + best(i+1, room-weights[i]) değerini verir. Büyük olanı al. Sığan her paketleme, paketleme ve atlama seçimlerinden oluşan bir dizidir ve özyineleme bunların hepsini dener.
Her öğe olası yolların sayısını ikiye katlar. 100 öğenin tümü birlikte sığdığında (örneğin her biri 10 ağırlığında ve çanta kapasitesi 1000 olduğunda) 2^100 yol vardır.
Algoritma
best(i, room)fonksiyonunu yaz;ison öğeyi geçtiğinde 0 döndür.skipdeğerinibest(i+1, room)olarak ayarla.weights[i] > roomiseskipdöndür.- Aksi takdirde
skipilevalues[i] + best(i+1, room-weights[i])değerlerinden büyük olanı döndür. best(0, capacity)değerini döndür.
def knapsack(weights, values, capacity):
n = len(weights)
# The most value items i, i+1, ... can add with room units of weight left
def best(i, room):
if i == n:
return 0
skip = best(i + 1, room)
if weights[i] > room:
return skip
take = values[i] + best(i + 1, room - weights[i])
return max(skip, take)
return best(0, capacity)Tabloyu öğe ve kapasiteye göre doldurun
Sezgi
Özyineleme, aynı (i, room) çiftine birçok yol üzerinden ulaşır. En fazla 101 × 1001, yani yaklaşık 10^5 çift vardır; bu yüzden her birini yalnızca bir kez hesaplayın.
best[i][c], ilk i öğenin kapasitesi c olan bir çantaya koyabileceği en yüksek değer olsun; 0. satırın tüm değerleri 0'dır. Ağırlığı w ve değeri v olan i-1. öğeyi dışarıda bırakmak best[i-1][c] değerini verir; w ≤ c olduğunda çantaya koymak ise best[i-1][c-w] + v değerini verir. i. satır yalnızca i-1. satırı okur, bu yüzden her öğe bir hücreye en fazla bir kez girer.
İlk örnekte, 2. öğe (ağırlık 3, değer 7) kapasite 7'deki değeri best[2][4] + 7 = 17'ye yükseltir. Ardından 3. öğenin sunduğu tek seçenek best[3][2] + 12 = 16 olur; bu yüzden yanıt 17 olarak kalır.
Algoritma
- n+1 satır ve capacity+1 sütundan oluşan, tüm değerleri 0 olan bir tablo oluştur.
- 1'den n'ye kadar her
isatırı içinw = weights[i-1]vev = values[i-1]değerlerini al. - Her kapasite
ciçinbest[i][c]değerinibest[i-1][c]olarak ayarla. w ≤ cise vebest[i-1][c-w] + vdaha büyükse, onun yerine bu değeri kaydet.best[n][capacity]değerini döndür.
def knapsack(weights, values, capacity):
n = len(weights)
# best[i][c]: the most value from the first i items within capacity c
best = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
w, v = weights[i - 1], values[i - 1]
for c in range(capacity + 1):
best[i][c] = best[i - 1][c] # leave item i-1 out
if w <= c and best[i - 1][c - w] + v > best[i][c]:
best[i][c] = best[i - 1][c - w] + v # put it in
return best[n][capacity]Tek satır, kapasiteler azalan sırayla tarandı
Sezgi
Satır i yalnızca i-1 satırına ihtiyaç duyar; bu yüzden best[c] adlı tek bir satırı tutup her öğede üzerine yazın. Yürüyüşün yönü, yanıtın doğru olup olmadığını belirler.
c yönünde yukarı doğru ilerlerken best[c-w], mevcut öğeyi zaten içerebilir. Ağırlığı 3 ve değeri 5 olan tek bir öğe, kapasite 6 iken kapasite 3'ü 5 değerinde yapar; ardından kapasite 6 bu değeri okur ve 10 olur: iki kopya. capacity değerinden w değerine doğru aşağı inildiğinde, okuduğunuz hücre yazdığınız hücrenin altında kalır ve daha sonra üzerine yazılır; bu nedenle önceki satırın değerini korur.
Öğelerden sınırsız sayıda kopya olduğunda yukarı doğru ilerlemek doğru döngüdür. Burada süre O(n × capacity) olarak kalır ve bellek tek satıra düşer.
Algoritma
- Tümü 0 olan,
capacity + 1girdilibest'i oluştur. - Ağırlığı
wve değerivolan her öğe içinc'yicapacity'denw'ye doğru azaltarak ilerle. best[c-w] + v,best[c]'den büyükse bunubest[c]'ye kaydet.best[capacity]'yi döndür.
def knapsack(weights, values, capacity):
# best[c]: the most value from the items seen so far within capacity c
best = [0] * (capacity + 1)
for w, v in zip(weights, values):
# Walk the capacities downward so each item goes in at most once
for c in range(capacity, w - 1, -1):
if best[c - w] + v > best[c]:
best[c] = best[c - w] + v
return best[capacity]
Tuzaklar ve uç durumlar
- Tek satırlı sürümde kapasite değerlerini artan sırayla dolaşmak, bir öğeyi iki kez yerleştirir: ağırlığı 3 ve değeri 5 olan bir öğe, kapasitesi 6 olan bir çantada 5 yerine 10 puan alır.
capacity + 1yerinecapacitygiriş içeren bir satır.best[capacity-1]değerini döndürmek, çantayı tam dolduran yerleştirmeleri göz ardı eder; örneğin, kapasitesi 1 olan bir çantaya ağırlığı 1 olan bir öğe yerleştirmek.- Giriş değerlerini eksi sonsuzdan başlatmak. Çantanın tamamen dolması gerekmez, bu yüzden tüm girişler 0'dan başlar; eksi sonsuz kullanıldığında üçüncü örnek 0 yerine eksi sonsuz döndürür.
- Çantadan daha ağır bir öğe atlanmalıdır. Üçüncü örnekte
w...capacitykapalı aralığı Swift'te programı durdurur ve(w+1):(capacity+1)R'de geriye doğru sayar.
Sıkça sorulan sorular3
0/1 sırt çantası probleminin zaman karmaşıklığı nedir?
Tablo O(n × capacity) zamanda çalışır; 100 öğe ve 1000 kapasite için yaklaşık 10^5 adım sürer ve tek satırlı sürüm O(capacity) bellek kullanır. Sınır sözde polinomaldir: kapasitenin basamak sayısına değil, değerine göre büyür. Genel problem NP-zordur.
0/1 sırt çantası problemi için açgözlü algoritma neden işe yaramaz?
Bir açgözlü kural, seçilen öğe hiçbir şeyi doldurmayan bir boşluk bıraksa bile seçimini asla geri almaz. Kapasite 7 iken, ağırlığı 5 ve değeri 10 olan öğe en iyi oran için eşitlik sağlar; ancak ağırlıkları 4 ve 3 olan öğelerin toplam değeri 13'tür. Orana göre açgözlü seçim yalnızca, öğeleri bölebildiğin kesirli sırt çantası probleminde en iyidir.
0/1 sırt çantasının hangi öğeleri seçtiğini nasıl bulursunuz?
Tam tabloyu sakla ve best[n][capacity] değerinden geriye doğru ilerle. best[i][c], best[i-1][c] değerinden farklıysa i-1 numaralı öğe çantaya konmuştur; bu yüzden onu kaydet ve ağırlığını c değerinden çıkar. Aksi hâlde aynı c ile i-1 satırına geç.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def knapsack(weights, values, capacity):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argümanlar
weights = [4, 2, 3, 5] values = [10, 4, 7, 12] capacity = 7
Beklenen Çıktı
17