Rod Cutting Problem

Q: Çubuk kesme probleminin zaman karmaşıklığı nedir?

Tablo O(n²) zaman ve O(n) bellek kullanır: len uzunluğu, ilk parçalar için len deneme yapar; toplamda n(n+1)/2 deneme yapılır. Saklanan yanıtlar olmadan özyineleme, n uzunluğundaki bir çubuk için tam olarak 2^n çağrı yapar; çünkü her uzunluk, kendisinden kısa tüm uzunluklar için çağrı yapar.

Q: Çubuk kesme neden sınırsız sırt çantası problemidir?

Her k uzunluğundaki parçayı ağırlığı k ve değeri prices[k-1] olan, sınırsız sayıda kullanılabilen bir eşya olarak ele al; çubuğu da tam olarak doldurulması gereken, kapasitesi n olan bir çanta olarak düşün. Eşyaların en yüksek toplam değeri, çubuk için en iyi fiyattır.

Q: Çubuğu nereden keseceğini nasıl bulursun?

Her uzunluk için, en iyi fiyatı sağlayan ilk parçayı k olarak kaydedin. n uzunluğundan başlayın: kaydedilen uzunlukta bir parça kesin, kalan uzunluğa geçin ve 0'a ulaşana kadar tekrarlayın. Parçalar, en iyi planı oluşturur.

OrtaDinamik programlama

+10

Uzunluğu n olan bir çubuğun var; burada n = prices.length. Uzunluğu k olan bir parça prices[k-1] fiyatına satılır. Çubuğu istediğin sayıda tam uzunlukta parçaya bölebilir veya tek parça hâlinde satabilirsin. Çubuğun tamamını satarak kazanabileceğin en yüksek tutarı döndür.

Fonksiyon

cutRod(prices: integer-array) → integer

pricesinteger-array: prices[k-1], uzunluğu k olan bir parçanın fiyatıdır; çubuğun uzunluğu prices.length kadardır
Döndürürinteger: tüm çubuğun kazanabileceği en fazla para

Kısıtlar

1 ≤ prices.length ≤ 1000
1 ≤ prices[i] ≤ 10⁵

Örnekler

Girdi: prices = [2, 5, 7, 8]
Çıktı: 10
Açıklama: Uzunluğu 2 olan iki parça 5 + 5 = 10 kazandırır. Çubuğu bütün hâlde satmak 8 kazandırır; 1 uzunluğunda bir parça ile 3 uzunluğunda bir parça ise 2 + 7 = 9 kazandırır.

Ek soru

Peki çubuğu en fazla m kez kesebiliyorsanız? O zaman her tablo girdisinin neyi bilmesi gerekir?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

n uzunluğunda bir çubuğun 2^(n-1) farklı kesilme şekli vardır. Bunların hepsine hiçbir zaman ihtiyaç duymazsın: ilk parça ne olursa olsun, geriye kalan daha kısa bir çubuktur ve aynı soruyu sorar. Dolayısıyla yalnızca n+1 yanıt vardır; her uzunluk için bir tane. Bunları en kısadan başlayarak hesaplamak O(n²) adım sürer.

İlk parça için her uzunluğu dene

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Plan ne olursa olsun, sol uçtaki parçanın uzunluğu 1 ile çubuğun uzunluğu arasında bir k değeridir ve prices[k-1] kazandırır; planın geri kalanı, uzunluğu length-k olan bir çubuğu keser. Bu nedenle best(length), uzunluk 0 için 0'dır; aksi hâlde, tüm k değerleri için prices[k-1] + best(length-k) ifadelerinin en büyüğüdür; burada k = length çubuğun bütün hâlde satılması anlamına gelir. Her planın ilk parçası vardır, dolayısıyla bu maksimum tüm planları kapsar.

Her çağrı, daha kısa tüm uzunluklar için dallandığından çağrı sayısı, uzunluğun her bir birimiyle iki katına çıkar: uzunluğu 40 olan bir çubuk yaklaşık 2^40, yani 10^12 çağrıya yol açar.

Algoritma

best(length) fonksiyonunu yaz; length 0 olduğunda 0 döndürsün.
1 ile length arasındaki her ilk parça k için prices[k-1] + best(length-k) değerini hesapla.
Bu değerlerin en büyüğünü döndür.
best(n) değerini döndür.

def cutRod(prices):
    # The most money a rod of this length can earn
    def best(length):
        top = 0
        for piece in range(1, length + 1):
            # sell a first piece of this length, then cut the rest as well as possible
            top = max(top, prices[piece - 1] + best(length - piece))
        return top

    return best(len(prices))

Her uzunluk için en iyi fiyat, en kısadan başlayarak

Sezgi

Özyineleme aynı değerleri yeniden hesaplar: best(2), best(3), best(4) ve daha uzun her çubuk tarafından istenir. Yalnızca n+1 uzunluk olduğundan, her birini bir dizi best içine bir kez hesaplayın. Bir uzunluk yalnızca daha kısa uzunlukları okur; bu yüzden diziyi 0'dan yukarı doğru doldurmak, her değer okunduğunda hazır olmasını sağlar.

[2, 5, 7, 8] için: best[1] 2'dir, best[2] 2 + 2 ile 5'ten büyük olanıdır, yani 5'tir, best[3] 7'dir ve best[4] 2 + 7, 5 + 5, 7 + 2 ve 8 arasındaki en büyük değerdir, yani 10'dur.

0/1 sırt çantasından farklı olarak, best[len-k] zaten k uzunluğunda parçalar içerebilir ve istediğiniz de budur; çünkü bir uzunluk istediğiniz kadar çok kesilebilir. len uzunluğu, ilk parça için len seçeneği dener: toplamda n(n+1)/2 adım, 1000 uzunluğunda bir çubuk için yaklaşık 5 × 10^5.

Algoritma

Tüm değerleri 0 olan, n + 1 elemanlı best oluştur.
1'den n'ye kadar her length için, 1'den length'e kadar her ilk parça k'yı dene.
prices[k-1] + best[length-k] değerini hesapla ve en büyüğünü best[length] içinde tut.
best[n] değerini döndür.

def cutRod(prices):
    n = len(prices)
    # best[length]: the most money a rod of that length can earn
    best = [0] * (n + 1)
    for length in range(1, n + 1):
        for piece in range(1, length + 1):
            # a first piece of this length, then the best for what is left
            earned = prices[piece - 1] + best[length - piece]
            if earned > best[length]:
                best[length] = earned
    return best[n]

Tuzaklar ve uç durumlar

k uzunluğu için prices[k] değerini okumak. Böylece her parçayı olması gerekenden bir boy uzun fiyatlandırır ve k = n olduğunda dizinin sonunu aşar; prices[k-1] kullan.
Kesilmemiş parça olan k = length durumunu dışarıda bırakmak. Böylece best[1] 0 kalır ve [1, 3, 8] dizisi 8 yerine 3 puan alır.
Birim başına en iyi fiyata göre açgözlü biçimde kesmek. [2, 7, 11, 13] dizisinde, 3 uzunluğundaki parça birim başına en çok kazandırır; ancak bu parça için 11 ve artan parça için 2 toplamda 13 ederken, 2 uzunluğunda iki parça 14 eder.
Python'da yukarıdan aşağıya memoizasyon yapmak. Özyineleme hâlâ çubuğun uzunluğu kadar derine iner: 1000 uzunluğundaki bir çubuk 1001 çağrı iç içe geçirir ve varsayılan 1000 sınırını aşar. Diziyi aşağıdan yukarıya doldur.

Sıkça sorulan sorular4

Çubuk kesme probleminin zaman karmaşıklığı nedir?

Tablo O(n²) zaman ve O(n) bellek kullanır: len uzunluğu, ilk parçalar için len deneme yapar; toplamda n(n+1)/2 deneme yapılır. Saklanan yanıtlar olmadan özyineleme, n uzunluğundaki bir çubuk için tam olarak 2^n çağrı yapar; çünkü her uzunluk, kendisinden kısa tüm uzunluklar için çağrı yapar.

Çubuk kesme neden sınırsız sırt çantası problemidir?

Her k uzunluğundaki parçayı ağırlığı k ve değeri prices[k-1] olan, sınırsız sayıda kullanılabilen bir eşya olarak ele al; çubuğu da tam olarak doldurulması gereken, kapasitesi n olan bir çanta olarak düşün. Eşyaların en yüksek toplam değeri, çubuk için en iyi fiyattır.

Çubuğu nereden keseceğini nasıl bulursun?

Her uzunluk için, en iyi fiyatı sağlayan ilk parçayı k olarak kaydedin. n uzunluğundan başlayın: kaydedilen uzunlukta bir parça kesin, kalan uzunluğa geçin ve 0'a ulaşana kadar tekrarlayın. Parçalar, en iyi planı oluşturur.

Her kesim para gerektiriyorsa çözüm nasıl değişir?

Çubuğu bütün olarak satmak kesim gerektirmez; diğer tüm ilk parçalar ise bir kesim ekler. Bu nedenle best[len], prices[len-1] ile len değerinden küçük k değerleri için en büyük prices[k-1] + best[len-k] - cost değerinden büyük olanına dönüşür. Tablonun geri kalanı aynı kalır.

def cutRod(prices):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argüman

prices = [2, 5, 7, 8]

Beklenen Çıktı