Task minisuppli


#1

Avrei bisogno di alcune informazioni sull’interpretazione del testo:

  1. una confezione può contenere anche un solo minisupplì? (sembrerebbe di si)

  2. 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


#2
  1. Sembra di sì, ma in realtà è no, altrimenti il problema come dici te non è ben definito

Magari ad una certa aggiungo al testo l’assunzione “Le scatole contengono almeno 2 minisupplì” :stuck_out_tongue:

PS: ho controllato tra gli input e questa assunzione viene rispettata


#3

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

2 
2 4 

3
3 6 9

#4

Bonus: dimostra che il problema ammette una soluzione se e solo se \gcd(a_1,a_2,\dots,a_n)=1.


#5

La dimostrazione potrebbe essere la seguente:

  1. Tutti i numeri ottenibili sono una combinazione lineare dell’insieme dei formati (delle confezioni) e come tali divisibili per il loro MCD

  2. Di conseguenza non è possibile ottenere una quantità di minisuppli che non sia divisibile per MCD

  3. 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)


#6

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.


#7

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.


#8

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?


#9

Il limite superiore della confezione minima è 20, cito il testo:

Le scatole non contengono più di 20 minisupplì.

Ti eri perso questa assunzione oppure se per esempio le scatole sono 19 e 20 è molto lenta?


#10

In tutta sincerità me l’ero persa, e visto che è così posso dire che è veloce anche con valori molto più grandi.
Grazie per la pazienza.


#11

Ho appena aggiustato il testo, adesso nelle assunzioni viene scritto:

La risposta esiste ed è minore di 100.