Fractional Knapsack

Q: Qual è la complessità temporale del problema dello zaino frazionario?

Ordinare gli elementi in base al valore per peso costa O(n log n) e il riempimento richiede un solo passaggio, quindi il costo totale è O(n log n) con O(n) di spazio per l'ordinamento. Cercare l'elemento con la densità maggiore a ogni iterazione costa O(n²) .

Q: Come si risolve il problema dello zaino frazionario senza usare numeri in virgola mobile?

Con pesi positivi, a / b > c / d è lo stesso test di a × d > c × b , quindi confronta le densità moltiplicando in croce. Il valore migliore è un numero intero più una frazione, values[i] × room / weights[i] per l’elemento frazionato, quindi una divisione intera fornisce esattamente il risultato arrotondato per difetto.

MedioGreedy Ordinamento

+10

Hai n oggetti. L'oggetto i vale values[i] e pesa weights[i]. La tua borsa può contenere un peso totale massimo di capacity e puoi prendere qualsiasi parte di un oggetto: un pezzo dell'oggetto i che pesa w vale values[i] × w / weights[i].

Scrivi una funzione chiamata fractionalKnapsack che restituisca il valore totale massimo che la borsa può contenere, arrotondato per difetto a un numero intero.

Funzione

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

valuesinteger-array: il valore di ciascun elemento
weightsinteger-array: il peso di ogni elemento
capacityinteger: il peso massimo che la borsa può contenere
Restituisceinteger: il valore totale più grande che entra nella borsa, arrotondato per difetto

Vincoli

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

Esempi

Input: values = [40, 90, 30, 50]weights = [8, 30, 5, 20]capacity = 40
Output: 151
Spiegazione: Per unità di peso, gli oggetti valgono 5, 3, 6 e 2.5. Gli oggetti 2 e 0 entrano per intero per un valore di 70, lasciando spazio per altri 27; 27 delle 30 unità dell’oggetto 1 aggiungono 81, per un totale di 151.

Input: values = [10, 7]weights = [4, 3]capacity = 5
Output: 12
Spiegazione: L’elemento 0 vale 2,5 per unità e l’elemento 1 circa 2,33, quindi l’elemento 0 entra interamente per 10. Una delle 3 unità dell’elemento 1 aggiunge 7 / 3 e 12 e un terzo si arrotonda per difetto a 12.

Per approfondire

Riesci a trovare la risposta in tempo O(n), senza ordinare tutti gli elementi?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Poiché puoi tagliare gli oggetti, il problema è greedy, a differenza dello zaino 0/1: ogni unità di peso dovrebbe provenire dall’oggetto con il maggior valore per unità rimasto. Ordina in base a questa densità e riempi lo zaino in ordine. Confronta le densità moltiplicando in croce e arrotonda per difetto solo l’oggetto che tagli, così non viene mai memorizzata alcuna frazione.

Seleziona l'elemento più denso a ogni turno

Corretto, ma non termina sui test più grandi

Intuizione

Riempi il sacco partendo dall’oggetto più denso: prendilo intero se ci sta, altrimenti prendi la parte che riempie il sacco e fermati. Trova l’oggetto inutilizzato più denso esaminandoli tutti e confrontando values[i] × weights[j] con values[j] × weights[i] invece di dividere. Con pesi positivi è lo stesso test, ed entrambi i prodotti restano pari o inferiori a 10^8.

Partire dall’oggetto più denso è la scelta migliore: se un carico contiene una certa quantità di peso di un oggetto meno denso mentre un oggetto più denso non è stato ancora inserito completamente, sostituire quel peso con l’oggetto più denso non può ridurre il valore. Continua a fare sostituzioni e otterrai il carico con gli oggetti in ordine di densità decrescente.

Fino a n round esaminano ogni volta gli oggetti inutilizzati, per circa n²/2 = 12.5 milioni di confronti con n = 5000.

Algoritmo

Contrassegna ogni elemento come inutilizzato e imposta room = capacity e total = 0.
Finché c'è spazio, esamina gli elementi inutilizzati per trovare quello con la densità maggiore, confrontando le densità tramite moltiplicazione incrociata.
Se non rimane alcun elemento, fermati. Altrimenti, contrassegna quell'elemento come utilizzato.
Se ci sta, aggiungi il suo valore a total e sottrai il suo peso da room. Se non ci sta, aggiungi values[i] × room / weights[i] usando la divisione intera e fermati.
Restituisci total.

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

Ordina per valore per peso

Intuizione

La scansione trova ogni volta l’oggetto con la densità più alta, ma l’ordine non cambia mai tra un giro e l’altro. Ordina gli oggetti una sola volta, dal più denso al meno denso, usando lo stesso confronto con prodotti incrociati. Gli oggetti con la stessa densità possono essere in qualsiasi ordine, perché valgono uguale per unità.

Prendi gli oggetti interi finché ci stanno. Il primo che non ci sta è l’unico che tagli: aggiunge values[i] × room / weights[i], e la divisione intera arrotonda per difetto. Tutto ciò che viene prima è un numero intero, quindi arrotondare questo termine dà il risultato esatto. L’ordinamento ha costo O(n log n) e la scansione O(n).

Algoritmo

Crea un elenco degli indici degli oggetti e ordinali dal più denso al meno denso usando il confronto con moltiplicazione incrociata.
Imposta room = capacity e total = 0.
Per ogni oggetto in quell’ordine, se weights[i] ≤ room, aggiungi il suo valore e sottrai il suo peso da room.
Altrimenti aggiungi values[i] × room / weights[i] con divisione intera e fermati.
Restituisci total.

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

Trappole e casi limite

Ordinare solo per valore o solo per peso. Nel primo esempio, l’elemento che vale 90 è solo terzo per densità; prenderlo per primo lascia spazio per metà dell’elemento che vale 50, per un totale di 115 invece di 151.
Dividere prima di moltiplicare. Con valore 13, peso 7 e spazio 3, 13 / 7 * 3 con l’aritmetica intera dà 3, mentre 13 * 3 / 7 dà il risultato corretto, 5.
Aspettarsi che un elemento venga sempre tagliato. Nel terzo esempio ogni elemento entra e la risposta è la somma di tutti i valori, 13.

Domande frequenti3

Qual è la complessità temporale del problema dello zaino frazionario?

Ordinare gli elementi in base al valore per peso costa O(n log n) e il riempimento richiede un solo passaggio, quindi il costo totale è O(n log n) con O(n) di spazio per l'ordinamento. Cercare l'elemento con la densità maggiore a ogni iterazione costa O(n²).

Perché l'approccio greedy funziona per il problema dello zaino frazionario ma non per quello dello zaino 0/1?

Il frazionamento ti permette di scambiare il peso di un oggetto meno denso con quello di uno più denso. Senza frazionamento, un oggetto denso può lasciare spazio che nient'altro può occupare. Con valori 8, 11, 15, pesi 2, 3, 4 e capacità 7, scegliendo prima gli oggetti più densi si ottengono pesi 2 e 4 per un valore di 23, mentre i pesi 3 e 4 danno 26. La versione 0/1 richiede la programmazione dinamica.

Come si risolve il problema dello zaino frazionario senza usare numeri in virgola mobile?

Con pesi positivi, a / b > c / d è lo stesso test di a × d > c × b, quindi confronta le densità moltiplicando in croce. Il valore migliore è un numero intero più una frazione, values[i] × room / weights[i] per l’elemento frazionato, quindi una divisione intera fornisce esattamente il risultato arrotondato per difetto.

def fractionalKnapsack(values, weights, capacity):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomenti

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

Output atteso