Fractional Knapsack

Q: Kesirli sırt çantası probleminin zaman karmaşıklığı nedir?

Öğeleri ağırlık başına değere göre sıralamak O(n log n) maliyetlidir ve dolum tek geçişte yapılır; bu nedenle toplam maliyet O(n log n) , sıralama için gereken alan ise O(n) olur. Her turda en yoğun öğeyi taramak O(n²) maliyetlidir.

Q: Kesirli sırt çantası problemini kayan noktalı sayılar olmadan nasıl çözersiniz?

Pozitif ağırlıklarla, a / b > c / d testi a × d > c × b testiyle aynıdır; bu nedenle yoğunlukları çapraz çarparak karşılaştırın. En iyi değer, kesilen öğe için bir tam sayı ile bir kesrin toplamıdır: values[i] × room / weights[i] . Böylece tek bir tamsayı bölmesi, aşağı yuvarlanmış sonucu tam olarak verir.

OrtaAçgözlü Sıralama

+10

n öğen var. i öğesinin değeri values[i] ve ağırlığı weights[i] kadardır. Çantan toplamda en fazla capacity ağırlık taşıyabilir ve bir öğenin herhangi bir kısmını alabilirsin: ağırlığı w olan i öğesinin bir parçasının değeri values[i] × w / weights[i] kadardır.

Çantanın taşıyabileceği en yüksek toplam değeri en yakın alt tam sayıya yuvarlayarak döndüren fractionalKnapsack adlı bir fonksiyon yaz.

Fonksiyon

fractionalKnapsack(values: integer-array, weights: integer-array, capacity: integer) → integer

valuesinteger-array: her bir öğenin değeri
weightsinteger-array: her bir öğenin ağırlığı
capacityinteger: çantanın taşıyabileceği en fazla ağırlık
Döndürürinteger: çantaya sığan en yüksek toplam değer, aşağı yuvarlanmış

Kısıtlar

1 ≤ n ≤ 5000, burada n = values.length = weights.length
1 ≤ values[i], weights[i] ≤ 10⁴
1 ≤ capacity ≤ 10⁸

Örnekler

Girdi: values = [40, 90, 30, 50]weights = [8, 30, 5, 20]capacity = 40
Çıktı: 151
Açıklama: Ağırlık birimi başına eşyaların değerleri 5, 3, 6 ve 2.5'tir. 2 ve 0 numaralı eşyalar tamamen alınarak 70 değer elde edilir ve 27 kapasite kalır; 1 numaralı eşyanın 30 biriminden 27'si de 81 değer ekleyerek toplamı 151 yapar.

Girdi: values = [10, 7]weights = [4, 3]capacity = 5
Çıktı: 12
Açıklama: 0. öğenin birim başına değeri 2.5, 1. öğeninki ise yaklaşık 2.33 olduğundan 0. öğe tamamen alınır ve değerine 10 eklenir. 1. öğenin 3 biriminden biri 7 / 3 ekler ve 12 ve üçte bir aşağı yuvarlanarak 12 olur.

Ek soru

Tüm öğeleri sıralamadan, cevabı O(n) zamanda bulabilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Öğeleri kesebildiğin için bu problem, 0/1 sırt çantasından farklı olarak açgözlüdür: her ağırlık birimi, geriye kalanlar arasında birim başına en yüksek değere sahip öğeden gelmelidir. Bu yoğunluğa göre sırala ve çantayı sırayla doldur. Yoğunlukları çapraz çarparak karşılaştır ve yalnızca kestiğin öğeyi aşağı yuvarla; böylece hiçbir kesir saklanmaz.

Her turda yoğunluğu en yüksek olan öğeyi seçin

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

Sezgi

Çantayı en yoğun eşyadan başlayarak doldur: sığıyorsa eşyayı tamamen al, aksi takdirde çantayı dolduracak parçayı al ve dur. Bölme işlemi yapmak yerine values[i] × weights[j] ile values[j] × weights[i] değerlerini karşılaştırarak kullanılmamış eşyaların tümünü tarayıp en yoğun olanı bul. Ağırlıklar pozitif olduğunda bu aynı testtir ve her iki çarpım da 10^8 değerini aşmaz.

Önce en yoğun eşyayı almak en iyisidir: Bir yükte daha az yoğun bir eşyanın bir miktar ağırlığı varken daha yoğun bir eşya henüz tamamen alınmamışsa, bu ağırlığı daha yoğun eşyayla değiştirmek değeri düşüremez. Değiştirmeye devam edersen en yoğun eşyadan başlayan yüke ulaşırsın.

En fazla n tur boyunca her turda kullanılmamış eşyalar taranır; n = 5000 için yaklaşık n²/2 = 12.5 milyon karşılaştırma yapılır.

Algoritma

Her öğeyi kullanılmamış olarak işaretle, room = capacity ve total = 0 olarak ayarla.
Yer olduğu sürece, yoğunlukları çapraz çarpma yöntemiyle karşılaştırarak kullanılmamış öğeler arasından en yoğun olanı tara.
Hiç öğe kalmadıysa dur. Aksi takdirde o öğeyi kullanılmış olarak işaretle.
Sığıyorsa değerini total'a ekle ve ağırlığını room'dan çıkar. Sığmıyorsa tamsayı bölmesiyle values[i] × room / weights[i] değerini ekle ve dur.
total değerini döndür.

def fractionalKnapsack(values, weights, capacity):
    n = len(values)
    used = [False] * n
    total = 0
    room = capacity
    while room > 0:
        best = -1
        for i in range(n):
            # i is denser than best: values[i] / weights[i] > values[best] / weights[best], cross-multiplied
            if not used[i] and (best == -1 or values[i] * weights[best] > values[best] * weights[i]):
                best = i
        if best == -1:
            break  # every item is already in the bag
        used[best] = True
        if weights[best] <= room:
            total += values[best]
            room -= weights[best]
        else:
            total += values[best] * room // weights[best]  # the part that fits, rounded down
            room = 0
    return total

Ağırlık başına değere göre sırala

Sezgi

Tarama, en yoğun öğeyi tekrar tekrar bulur, ancak turlar arasında sıralama hiç değişmez. Öğeleri bir kez, en yoğun olan başta olacak şekilde ve aynı çapraz çarpım karşılaştırmasını kullanarak sırala. Yoğunlukları eşit olan öğeler herhangi bir sırada olabilir, çünkü birim başına değerleri aynıdır.

Sığdıkları sürece öğeleri bütün olarak al. Sığmayan ilk öğe, keseceğin tek öğedir: values[i] × room / weights[i] kadar değer ekler ve tamsayı bölmesi sonucu aşağı yuvarlar. Ondan önceki her şey tam sayıdır; bu nedenle bu tek terimi yuvarlamak kesin sonucu verir. Sıralama O(n log n), üzerinden geçme ise O(n) maliyetindedir.

Algoritma

Öğe indekslerinin bir listesini oluştur ve çapraz çarpımlı karşılaştırmayı kullanarak yoğunluğu en yüksek olandan başlayacak şekilde sırala.
room = capacity ve total = 0 olarak ayarla.
Bu sıradaki her öğe için, weights[i] ≤ room ise değerini ekle ve ağırlığını room değerinden çıkar.
Aksi hâlde, tam sayı bölmesiyle values[i] × room / weights[i] değerini ekle ve dur.
total değerini döndür.

from functools import cmp_to_key


def fractionalKnapsack(values, weights, capacity):
    # a goes before b when values[a] / weights[a] > values[b] / weights[b],
    # tested as values[a] * weights[b] > values[b] * weights[a] to stay in whole numbers.
    def denser_first(a, b):
        return values[b] * weights[a] - values[a] * weights[b]

    order = sorted(range(len(values)), key=cmp_to_key(denser_first))
    total = 0
    room = capacity
    for i in order:
        if weights[i] <= room:
            total += values[i]  # the whole item fits
            room -= weights[i]
        else:
            total += values[i] * room // weights[i]  # the part that fits, rounded down
            break
    return total

Tuzaklar ve uç durumlar

Yalnızca değere veya ağırlığa göre sıralama yapmak. İlk örnekte değeri 90 olan öğe, yoğunluk sıralamasında yalnızca üçüncü sıradadır; onu ilk almak, değeri 50 olan öğenin yarısı için yer bırakır ve 151 yerine 115 kazandırır.
Çarpmadan önce bölme yapmak. Değer 13, ağırlık 7 ve kalan kapasite 3 olduğunda, tam sayı aritmetiğinde 13 / 7 * 3 işlemi 3 verirken 13 * 3 / 7 doğru sonuç olan 5'i verir.
Her seferinde bir öğenin parçalanabileceğini düşünmek. Üçüncü örnekte tüm öğeler sığar ve yanıt tüm değerlerin toplamı olan 13'tür.

Sıkça sorulan sorular3

Kesirli sırt çantası probleminin zaman karmaşıklığı nedir?

Öğeleri ağırlık başına değere göre sıralamak O(n log n) maliyetlidir ve dolum tek geçişte yapılır; bu nedenle toplam maliyet O(n log n), sıralama için gereken alan ise O(n) olur. Her turda en yoğun öğeyi taramak O(n²) maliyetlidir.

Neden açgözlü yaklaşım kesirli sırt çantası probleminde işe yararken 0/1 sırt çantası probleminde işe yaramaz?

Kesirli alma, daha düşük yoğunluklu bir öğeden ağırlığı daha yoğun bir öğeye aktarmanı sağlar. Kesirli alma olmadan, yoğun bir öğe başka hiçbir şeyin dolduramayacağı bir alan bırakabilir. Değerler 8, 11, 15, ağırlıklar 2, 3, 4 ve kapasite 7 olduğunda, önce en yoğun olanı almak 23 değerinde 2 ve 4 ağırlıklarını seçerken, 3 ve 4 ağırlıkları 26 değerini verir. 0/1 sürümü dinamik programlama gerektirir.

Kesirli sırt çantası problemini kayan noktalı sayılar olmadan nasıl çözersiniz?

Pozitif ağırlıklarla, a / b > c / d testi a × d > c × b testiyle aynıdır; bu nedenle yoğunlukları çapraz çarparak karşılaştırın. En iyi değer, kesilen öğe için bir tam sayı ile bir kesrin toplamıdır: values[i] × room / weights[i]. Böylece tek bir tamsayı bölmesi, aşağı yuvarlanmış sonucu tam olarak verir.

def fractionalKnapsack(values, weights, capacity):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argümanlar

values = [40, 90, 30, 50]
weights = [8, 30, 5, 20]
capacity = 40

Beklenen Çıktı