Problema dello zaino con vincoli sui valori degli articoli

Question

Dato $n$ oggetti con pesi $w_1,...,w_n$ e valori $v_1,...,v_n$, e un limite di peso $W$, lo scopo è comunque quello di massimizzare il valore totale degli oggetti da trasportare (senza superare il limite di peso).Ora, un nuovo vincolo è, una volta, un oggetto con valore $v_i$ vengono presi tutti gli elementi il ​​cui valore è maggiore di $v_i$ bisogna anche prenderlo.(Va bene supporre tutto questo $v_i$sono diversi)

Il mio scopo è raggiungere questo obiettivo $O(n)$ tempo, ed ecco il mio tentativo (supponiamo che l'input sia un array $A$ di tuple $(w_i, v_i)$):

1. Calcolare il peso totale degli articoli: $W_{\mathrm{totale}}\gets \sum_{i=1}^n w_i$;

2. Mentre $(W_{\mathrm{totale}} > W)$ Fare:

   2.1 $p\ottiene$ mediana dei valori in $A$;

   2.2 $R\ottiene$ elementi il ​​cui valore è maggiore di $p$;

   2.3 $L\ottiene A\setmeno R$;(articoli il cui valore è inferiore a $p$)

   2.4 $W_R\ottiene $ $\somma_{A[i]\in R}w_i$;

   2.5 $W_{\mathrm{totale}}\gets W_R$;

   2.6 $A\ottiene R$;

3. $W\ottiene W- W_{\mathrm{totale}}$;(la capacità rimanente)

4. Ripetere il passaggio 2 per l'array $L$, generando l'array $L'$;

5. Ritorno $L' azza A$;

Si noti che l'algoritmo per trovare la mediana costa tempo lineare.

Presumo che il mio algoritmo costi $O(n)$ tempo da allora, per ogni iterazione in ciascun ciclo while, la dimensione dell'input si dimezza, ma non ne sono sicuro al 100%.Quindi questo algoritmo costa davvero tempo lineare?In caso contrario, quali modifiche si possono apportare o esiste un'idea generale per progettare un algoritmo che costi tempo lineare?Qualsiasi aiuto sarà molto apprezzato!:)

Answer 1

Sì, il tuo algoritmo viene eseguito $O(n)$ tempo se si utilizza l'algoritmo della mediana delle mediane.Puoi dimostrarlo a te stesso osservando il tuo algoritmo e notando che in ogni ciclo la dimensione dell'array che stiamo considerando viene dimezzata.E il tempo di esecuzione del corpo del ciclo è $O(n)$ (se usiamo la mediana delle mediane e la copia/filtro dell'array è $O(n)$ Comunque).Ora otteniamo la seguente somma:

$$\sum_{i=0}^{\log(n)} \frac{n}{2^i} \leq \sum_{i=0}^{\infty} \frac{n}{2^i } = n\cdot\sum_{i=0}^{\infty} \frac{1}{2^i} = 2n \in O(n)$$

IL $\log(n)$ deriva dal fatto che puoi solo dividere la dimensione dell'array $log(n)$ volte a metà fino ad arrivare a $1$ (Perché $2^{\log(n)} = n$).Ogni termine della somma esprime il costo di un'esecuzione del corpo del ciclo.