Algoritmo per abbinare gli elementi essere valore in insiemi di base sul totale

Naviga le tue risposte
1

Dato n set di elementi. Ogni oggetto ha un valore. Gli articoli in un set hanno valori simili ma variano di una piccola quantità. L'obiettivo è creare nuovi set contenenti tre elementi selezionati dai set originali in modo tale che il totale dei valori sia compreso in un determinato intervallo. È possibile selezionare solo un elemento per un set di origini.

Ad esempio: se abbiamo i seguenti set iniziali:

  • Imposta A - {4.0, 3.8, 4.2}
  • Imposta B - {7.0, 6.8, 7.2}
  • Imposta C - {1.0, 0.9, 1.1}
  • Imposta D - {6.5, 6.4, 6.6}
  • Imposta E - {2.5, 2.4, 2.6}

L'obiettivo è creare set contenenti tre elementi in modo tale che il totale sia compreso tra 11.9 e 12.1.

  • Ad esempio {3.8, 7.2, 1.0}

Possono esserci elementi non utilizzati.

Qualcuno può suggerire un algoritmo per questo problema?

    
posta Ben 18.08.2014 - 19:05
fonte

2 risposte

2

Questo sembra un problema tipo zaino. Nessuna scorciatoia.

Forma una permutazione di ciascuna delle possibili selezioni, enumerale e scegli quelle che rientrano nell'intervallo.

La definizione del problema potrebbe essere migliorata specificando esattamente come vengono effettuate le selezioni, ad esempio una per ogni set?

    
risposta data 19.08.2014 - 07:02
fonte
1

Se devi usare esattamente 3 elementi, allora è il peggiore problema O (n ^ 2 log n). Inserisci tutti gli elementi in una struttura ordinata (O (n log n)). Quindi scorrere tutte le possibili coppie di somme (O (n ^ 2)). Per ogni coppia somma la ricerca dell'albero per vedere se c'è un terzo elemento adatto (O (log n)).

Se puoi usare un numero arbitrario di elementi, ma i valori sono positivi e possono essere ridotti a numeri interi piccoli (come sopra, moltiplica tutti per 10), puoi usare la programmazione dinamica per ottenere una soluzione nel tempo O ( n * s) dove s è la somma desiderata.

Vedi link

    
risposta data 19.08.2014 - 07:18
fonte

Leggi altre domande sui tag

Domanda su derisione esterna [duplicato] Come lasciare che il mondo esterno decori il mio campo privato?