Dato un sottoinsieme di numeri e sottoinsiemi di somme. Abbina i numeri alle somme. (Più difficile di appare)

Question

Dato un sottoinsieme di numeri e sottoinsiemi di somme. Abbina i numeri alle somme. (Più difficile di appare)

#1 da (1 voti)

-2

Non sono sicuro di quale sia la soluzione più efficace per questo algoritmo. Non sono sicuro che questo si adatti alla copertura esatta, e avvicinarsi attraverso un backtracking esauriente sembra in qualche modo inefficiente. Qualche suggerimento su come affrontare questo?

There are 210 Invoices and 1700 bills – these bills add up to these invoices

The association between bills and invoices is lost . The only way to match them is by adding them up to correct amounts that are equal to the invoices.

Ad esempio, considera il caso in cui hai 2 fatture per 80, 210 e hai fatture per i valori 50, 10, 10, 30, 20, 70, 100.

Una delle possibili soluzioni è:

80 = 50 + 30

210 = 10 + 10 + 20 + 70 + 100

Un'altra possibile soluzione è

80 = 50 + 10 + 20

210 = 30 + 20 + 70 + 100

Qual è il modo migliore per ottenere tutte le soluzioni? Ricorda che hai a che fare con grandi set di dati.

algorithms

posta emc_two88 28.09.2014 - 09:14

fonte

1 risposta

Leggi altre domande sui tag algorithms

Dovremmo incorporare macchine virtuali piuttosto che lingue I Web Framework si preoccupano della persistenza?

score 1 · Answer 1

Questo problema è più difficile che risolverlo per 2 fatture (raggruppa tutte le fatture tranne una). Se proviamo a risolverlo per 2 fatture e 1700 fatture, vediamo che la somma delle 2 fatture è uguale alla somma delle 1700 fatture, quindi tutto ciò che dobbiamo trovare è un sottoinsieme delle 1700 fatture la cui somma è uguale a una le fatture. Quindi abbiamo un problema di sottoinsieme, il che significa che si tratta di un problema NP-difficile. Quindi, a meno che non abbiamo una ragionevole limitazione su quali valori le fatture possano prendere questo problema non è risolvibile in un ragionevole lasso di tempo.

La risposta è quindi che questo problema non è risolvibile con le informazioni fornite. Tuttavia, se supponiamo che la fattura più grande sia ragionevolmente piccola, possiamo utilizzare la programmazione dinamica per risolvere questo problema.