Come distribuire un numero di elementi in un bucket in modo che rientri in un intervallo?

Question

Come distribuire un numero di elementi in un bucket in modo che rientri in un intervallo?

#1 da (2 voti)
#2 da (1 voti)

5

Ho 50 elementi n1, n2, n3, ..., n50 e un numero limitato di bucket, diciamo 5 bucket e ciascun bucket può contenere un intervallo, diciamo solo da 100 a 150 (che non è altro che la somma di gli elementi in quel secchio), ma né meno di 100, né più di 150.

Quale algoritmo è più adatto per risolvere questo problema, in modo tale che tutti i 5 bucket siano utilizzati e tutti gli elementi (n1, n2, n3, ...) vengano utilizzati anche?

Se non è possibile utilizzare un bucket o se un elemento deve essere escluso, l'algoritmo deve solo restituire "InvalidConditionsFound".

Ho provato lo zaino che ti dà una combinazione il più vicino possibile a un determinato numero, ma come ottenerlo entro un raggio e assicurarti che scelga saggiamente in modo tale che tutti i secchi si riempiano, e non che due secchi ottengano 150 pieno e l'altro secchio è solo a, diciamo 50?

java algorithms optimization

posta Argho Chatterjee 06.10.2015 - 12:29

fonte

2 risposte

Leggi altre domande sui tag java algorithms optimization

In Web API è una buona pratica avvolgere i risultati con il mio modello? [chiuso] Consenti thread (in c) per stampare messaggi senza interferire con l'input dell'utente

score 2 · Answer 1

50 elementi x 5 secchi? Quelli sono numeri piccoli. Probabilmente un'euristica di backtracking a forza bruta funzionerà. Ordinarli, aggiungere elementi ai bucket cercando di mantenere i totali del bucket uguali. Se non si ottiene una soluzione in un solo passaggio, quindi back-track.

Una volta ho usato un processo simile per assegnare i pallet di merci ai camion. L'obiettivo era di ridurre al minimo il numero di camion necessari per contenere tutti i pallet. Ogni carrello aveva una capacità di carico massima (e un limite di pallet). Per prima cosa ho seguito Best-Fit-First per caricare il numero minimo teorico di camion. Se avessi lasciato i pallet, ho trovato i due camion più vuoti e ho fatto un repacking forza bruta per vedere se potevo spremere in un altro pallet. Questo algoritmo ha imballato con successo 200 pallet con un peso totale di 499.000 sterline in 10 camion con una capacità di 50.000 sterline ciascuno.

score 1 · Answer 2

Hai K bucket, attualmente cinque.

Ordina i tuoi valori di input positivi e trova la loro somma, s . Verifica 100 × K ≤ s ≤ 150 × K o annulla subito.

Elabora avidamente ogni valore di input, dal più grande al più piccolo, e assegnalo a un bucket. In una variante dell'algoritmo, deterministicamente assegnarlo al bucket attualmente più leggero. In una variante più costosa, assegnala a caso a un bucket idoneo e preparati per una certa quantità di backtracking o tentativi se le cose non si risolvono inizialmente.