Algoritmo per riempire gli slot

Question

Sto cercando un algoritmo per riempire più slot, che sono già riempiti ad un certo livello.

• I livelli attuali e la quantità disponibile per riempire sono noti
• livelli risultante deve essere il più possibile uguali, ma il livello esistente non possono essere ridotti
• scanalature sono riempite da sinistra a destra, slot così sinistra ottengono livello superiore se uguale livello è impossibile

          Examples http://img695.imageshack.us/img695/6529/fill.png

L'immagine in alto mostra sei esempi, ogni colonna rappresenta uno slot. L'area grigia è già piena, il blu è la posizione prevista dei nuovi elementi.

---

ho potuto scorrere le fessure e aumentare la quantità sullo slot più basso dal 1 fino a quando la quantità disponibile è consumato, ma mi chiedo su come in realtà calcolare i nuovi livelli di riempimento.

ho intenzione di perseguire questo obiettivo con SQL/PL/SQL, altro codice è altrettanto gradito però :)

Answer 1

suona come il classico Knapsack problem C'è un certo numero di diverse soluzioni di lingua per questo utilizzando diversi algoritmi a Rosetta Code se io Non sono sicuro che ci sia qualcosa in PL/SQL

Answer 2

Forse un algoritmo avido con la randomizzazione per rompere i legami sarà sufficiente.

Sia n il numero di slot che è necessario compilare.

Passaggio 1: scorrere le colonne per identificare le colonne che presentano il minor numero di slot riempiti. Salta le colonne già riempite.

Passaggio 2: se nessuna delle colonne identificate nel passaggio 1 è maggiore di una, selezionare una a caso.

Passo 3: Impostare n = n-1

ripetere i punti 1, 2 e 3 fino a n = 0 o non si dispone di tutte le colonne vuote.

Answer 3

Questo è piuttosto semplice.

È possibile visualizzarlo come un getto d'acqua e lasciarlo riempire, tranne che in alcuni casi *.

1. Ordina. Puoi anche usare una coda di priorità.
2. Tieni traccia del numero di colonne min correnti.
3. Ottieni la colonna minima con la seconda colonna min.
4. Riempire la colonna min con il numero di articoli disponibili o fino alla seconda colonna min.
5. Incrementa il conteggio delle colonne min correnti.
6. Passare al punto 4 finché tutte le colonne non si trovano allo stesso livello, tranne utilizzare il numero di articoli disponibili o delta (secondo min - primo minuto) moltiplicato per il numero di colonne min correnti. Se il numero di elementi disponibili non è sufficiente, basta fare semplici calcoli matematici (divisione e resto) per riempire le colonne e usare il resto per riempire da sinistra.
7. Quando tutte le colonne sono sullo stesso livello, utilizzare la semplice parte matematica descritto al punto 6.

si dovrebbe essere buono.

Questo algoritmo viene eseguito nel tempo O(n log n).

* alcuni casi questo non ha senso, ma si sarebbe ancora voglia di farlo comunque:

# 
# 
## 
### 
### 

In tal caso, si dovrebbe riempire la terza colonna, poi il primo, poi il secondo, ma ovviamente non riempie abbastanza acqua.

Answer 4

1. Ordinare le colonne dal livello di inizio più basso a quello più alto.
2. Calcola l'utilizzo iniziale cumulativo per le colonne (ordinate).
3. Calcola per ogni colonna la quantità di riempimento nuova che verrà utilizzata riempiendo fino all'altezza di tale colonna. L'importo utilizzato sarebbe l'altezza della colonna per l'indice della colonna, meno l'uso iniziale cumulativo di tutte le colonne precedenti.
4. Scegli la colonna con indice i che utilizzerà la maggior parte del tuo nuovo riempimento senza andare oltre. Riempi tutte le colonne fino alla colonna i fino all'altezza della colonna i (che utilizzerà la quantità di riempimento calcolata al passaggio n. 3 per la colonna i), quindi il riempimento rimanente si posiziona sulle prime colonne ugualmente floor(remaining/i) più un riempimento aggiuntivo sul primo remaining % i colonne.
5. Annulla tipo di colonne per ottenere risultato.

Questo dovrebbe richiedere un tempo lineare nel numero di colonne (indipendente dalla quantità di riempimento).