Che tipo di algoritmo risolve questo problema semplice?

[Alello]

Ho un budget di 10 euro, e con questo budget devo comprare 20 caramelle.

Devo comprare obbligatoriamente 5 caramelle del tipo A, 10 del tipo B e 5 del tipo C. Posso comprare più volte la stessa caramella.

(Ogni caramella è identificata da una coppia di valori, il costo e il grado di bontà/qualità, caramelle dello stesso tipo possono avere coppia di valori diversi)

In che modo riesco a giungere alla combinazione ottimale?
Per combinazione ottimale si intende le 20 caramelle che riesco ad acquistare con 10 euro che mi diano un grado di bontà/qualità totale maggiore. Posso comprare più volte la stessa caramella.

Qual'è l'algoritmo che serve a me? (Ho dato un'occhiata agli algoritmi studiati in ricerca operativa per grafi, percorsi minimi, ecc. ma non ho trovato nulla)


Inoltre, quando mi ritrovo di fronte a questi problemi, non riuscendoci ad arrivare logicamente, qual'è il metodo migliore per ricercare la soluzione?

Grazie


p.s. Adesso sto dando un'occhiata al problema del consumatore e della scelta ottima del paniere...

Calcolando per ogni caramella il grado di appetibilità, ovvero il rapporto qualità prezzo (qualità/costo) si riesce ad ordinare le caramelle più convenienti per ogni tipo. Ovviamente prendendo le 5 caramelle più convenienti per ogni tipologia si potrebbe non spendere l'intero budget, oppure sforare il budget.

Inoltre si deve tener conto della relazione tra i vari tipi di caramelle, cioè rinunciare ad una certa caramella di tipo A mi permetterebbe di acquistare una caramella di tipo B che mi permetterebbe di raggiungere la scelta ottimale.

[Alello]

Originariamente inviato da Antonio23

ottmizzazione vincolata?

Ci do un'occhiata grazie

[OoZic]

ho l'impressione che il problema sia mal posto.

se hai 3 tipi di caramelle con 3 tipi di bontà e sei obbligato a comprare 5 A, 10 B e 5 C e hai un massimo di 20 caramelle, non c'è niente da ottimizzare.

la bontà totale sarà data da bontàA*5+bontàB*10+bontàC*5.

[Alello]

Originariamente inviato da OoZic

ho l'impressione che il problema sia mal posto.

se hai 3 tipi di caramelle con 3 tipi di bontà e sei obbligato a comprare 5 A, 10 B e 5 C e hai un massimo di 20 caramelle, non c'è niente da ottimizzare.

la bontà totale sarà data da bontàA*5+bontàB*10+bontàC*5.

Si però tra le caramelle di tipo A vi rientrano varie caramelle, ed ognuna ha un costo e un grado di bontà diverso.

p.s. Hai ragione, era spiegato male. Ho corretto, grazie.

[OoZic]

in questo caso ipotizzando che
A1,A2,A3,A4... sono le varie tipologie caramelle di tipo A e analogamente B1,B2...B1,B2 puoi metterlo cosi

A(n) = quantità di quella caramella di tipo A
x(n) = bontà di quella caramella di tipo A

B(n) = quantità di quella caramella di tipo B
y(n) = bontà di quella caramella di tipo B

C(n) = quantità di quella caramella di tipo C
z(n) = bontà di quella caramella di tipo C

obiettivo
max sommatoria A(n)*x(n) + B(n)*y(n) + C(n)*z(n)

vincoli
sommatoria A(n) = 5
sommatoria B(n) = 10
sommatoria C(n) = 5
A(n) + B(n) + C(n) = 20 anche se è un vincolo ridondante credo in quanto si deduce già dai 3 sopra.
A,B,C numeri interi positivi (altrimenti ti salta fuori un valore 0,7 A che non ha senso )

per quanto riguarda un algoritmo mi pare di ricordare che per l'ottimizzazione intera quelli più gettonati sono branch & bound, piani di taglio, gomory.

però sono cose che ho studiato tempo fa e non ricordo benissimo...
tra l'altro casualità vuole che quell'esame non l'ho passato e devo darlo a settembre quindi a breve ricomincerò a studiarlo

[banryu79]

A me sembra un tipico problema di Linear Optimization (o Linear Programming).

[marco.r]

E' il cosiddetto problema dello zaino
https://en.wikipedia.org/wiki/Knapsack_problem

dovresti trovare tutto quello che ti serve nel tuo libro di testo (o con due clic partendo dalla pagina qui sopra...)