Avrei bisogno di alcune informazioni sull’interpretazione del testo:
una confezione può contenere anche un solo minisupplì? (sembrerebbe di si)
in una combinazione di confezioni una stessa confezione può comparire più volte?
Mi sembra che se vale la seconda e c’è una confezione da 1 il problema non ammetta soluzione
nel senso che non esiste una quantità di minisuppli che non può essere venduta (oppure questa quantità vale 0?), se non vale la seconda mi sembra che la soluzione dell’esempio non sia 6.
Forse è vera la seconda ma non la prima?
Grazie
Bisognerebbe anche specificare che negli inpiu una soluzione esiste sempre, anche se sono molti casi in cui non esiste.
Tutte le misuere sono pari oppure le misure sono tutti multipli/divisori di tutte le altre misure
Tutti i numeri ottenibili sono una combinazione lineare dell’insieme dei formati (delle confezioni) e come tali divisibili per il loro MCD
Di conseguenza non è possibile ottenere una quantità di minisuppli che non sia divisibile per MCD
Quindi se MCD>1 l’insieme di queste quantità non ha un limite superiore e il problema non ammette soluzione (ad esempio un qualunque numero primo diverso da MCD non è ottenibile)
Partendo dal pressuposto che, se tutti le misure sono miltiple di uno stesso numero K, andando poi a sommare multipli di K si ottengono solamente multipli di K che saranno ad un distanza di K numeri(ogni K numeri, K-1 non verranno presi), quindi esiste una soluzione quando K-1=0 quindi K=1.
Essendo m=gcd(a_1,a_2,\dots,a_n)=1 significa che non esiste alcun K!=1 da uno e quindi esiste una soluzione a questo problema.
Puoi scrivere ogni misura come K*(V[i]/K) e sommando 2 o più misure si ottiene: K*(V[i]/K)+...+K*(V[y]/K) = K*(V[i]/K+...+V[y]/K) ottenendo solo multipli di K.
La mia soluzione diventa molto lenta se la confezione minima è di valore abbastanza alto.
E’ la mia che è scarsetta o è necessario mettere un limite superiore al valore della confezione minima?