Vicino al problema dello zaino?

Naviga le tue risposte
2

Penso che sto cercando di risolvere un problema in qualche modo simile a un problema con lo zaino. Non sono sicuro però.

Vedi l'input fornito di seguito e la mia soluzione. Ci sono tre tipi di oggetti e 4 secchi. Il problema è di mantenere gli articoli il più uniformemente possibile nei 4 secchi. cioè la capacità dei secchi (o il numero di oggetti nel secchio) dovrebbe essere uguale (o quasi uguale). Puoi anche mantenere gli articoli di diversi tipi nello stesso bucket.

input di esempio: 

item-type   :   A   B   C
  #items    :   12  36  25

Una soluzione semplice che sto usando al momento è la seguente:

  1. Dato che ci sono 4 bucket, ciascun bucket dovrebbe ottenere (sum of items)/4 . Per i dati di input di esempio sopra, è (12 + 36 + 25)/4 , cioè circa 18 articoli. La capacità di ciascuno dei bucket dovrebbe essere "CLOSE" a 18.

  2. Quindi inizia a mantenere gli elementi di tipo A nel primo bucket fino a quando il numero di elementi diventa 18. Tuttavia, abbiamo ancora bisogno di altri 6 elementi per il primo bucket dato che il numero di elementi di tipo A è 12. Pertanto tieni 6 articoli del tipo B nel primo bucket in modo che la capacità del primo bucket sia pari a 18. Come questo, riempire anche gli altri tre bucket.

Infine i quattro bucket sono i seguenti: 

Bucket-1: (12 A items, 6 B items)
Bucket-2: (18 B items)
Bucket-3: (12 B items, 6 C items)
Bucket-4: (19 C items).

Penso che la complessità temporale di questo problema sia O (N ^ 2) , N è il numero di bucket.

Sarebbe bello se qualcuno mi aiutasse a migliorare ulteriormente la soluzione.

Note-1 : possiamo mescolare elementi di tipi diversi nello stesso bucket.

Nota 2 : dobbiamo anche mantenere in qualche modo le informazioni sul tipo di elemento nel bucket.

    
posta samarasa 01.05.2015 - 07:02
fonte

3 risposte

2

Sembra che tutti i tuoi articoli abbiano le stesse dimensioni, nel qual caso la soluzione è banale. Contare il numero totale di articoli, diciamo che il numero è c. Diciamo che ci sono n secchi. Calcola x = piano (c / n) e y = c - n * x. Quindi i contenitori y vengono riempiti con x + 1 elementi e i bin n-y sono riempiti con x elementi.

Per rendere questo un problema interessante, supponiamo che i diversi tipi di articoli abbiano dimensioni diverse, e supponiamo che questa volta il totale di tutti i pesi sia c. In tal caso, è possibile che non sia possibile distribuire gli articoli in contenitori con pesi x e x + 1. O che è difficile farlo. Se è impossibile, allora dovresti definire qual è la soluzione "migliore".

    
risposta data 01.05.2015 - 19:32
fonte
3

Per le quantità di articoli A, B, C e la quantità di secchi N, ciascun segmento dovrebbe rimanere vicino a A / N + B / N + C / N, rispettivamente di ciascun tipo. La messa effettiva degli oggetti dovrebbe richiedere O (N).

Puoi distribuire gli oggetti mod N + B mod N + C mod N leggermente irregolari tra i bucket usando la scelta round-robin: metti un oggetto rimanente di tipo A nel secchio # 1, il rimanente articolo di tipo B nel secchio # 2, ecc., avvolgere nel secchio n. 1 secondo necessità. Un uso intelligente dell'operatore mod dovrebbe rendere questo anche O (N).

    
risposta data 01.05.2015 - 07:31
fonte
1

Non vorresti iterare il numero di elementi totali e non di bucket ^ 2?

Ad esempio, 

item[0] goes into bucket 1.
item[1] goes into bucket 2.
item[2] goes into bucket 3.
item[3] goes into bucket 4.
item[4] goes into bucket 1.

Alcune cose a cui pensare: Ogni elemento ha una proprietà, tipo-elemento come parte della sua definizione? Ad esempio, conosci un marmo rosso, è rosso. Gli articoli sono ordinati?

    
risposta data 01.05.2015 - 07:38
fonte

Leggi altre domande sui tag

Se ho un metodo che necessita di verifica per poter procedere, lo chiamo all'interno del metodo o prima? [duplicare] Log delle modifiche completo o parziale per il rilascio