Salve a tutti!
Chiedo cortesemente aiuto per questo esercizio di algoritmi... premetto che lo sto studiando ora all'università, ma sto cercando di portarmi avanti con la materia e mi sono imbattuto in questo grattacapo.
Allora... chiede di determinare la differenza derivante dalla più equa divisione di un tot. di monete tra due persone in base al loro valore. Sia il numero di monete che i valori delle monete li prende da input, il numero di monete può essere al massimo 100 ed il valore delle monete delle monete varia da 1 e 500.
Es. 1 2 3 | differenza = 0
Es. 1 2 4 6 | differenza = 1
Inizialmente ho provato ad inserire i valori in una lista, ordinarla e poi da li partire con la distribuzione dalla moneta di più alto valore in giù, salvandomi le somme delle distribuzioni in due interi, in questo modo:
monete.sort();
suddivisione1 = 0;
suddivisione2 = 0;
differenza = 0;
while(!monete.empty()) {
monetaCorr = monete.back();
monete.pop_back();
if(differenza >= 0) {
differenza -= monetaCorr;
suddividisione1 += monetaCorr;
} else {
differenza += monetaCorr;
suddividisione2 += monetaCorr;
} // if.
} // while.
differenza = abs(differenza1 - differenza2);
Putroppo mi sono reso conto che non funziona sempre... ho provato a fare in un altro modo, funge, ma è troppo oneroso, cioè quello di generare tutte le possibili combinazioni di distribuzioni!
Quindi chiedo come posso renderlo più efficiente... leggendo un pò in giro, questo problema è tipico della programmazione golosa, spero di non sbagliarmi, ma non riesco ad applicarla! Grazie per l'attenzione!