Esercizio in c++ indicazioni help me!!

[Aleb65]

Luca, stanco del duro lavoro di consulenza a cui è stato sottoposto recentemente, può finalmente rilassarsi a pranzo dalla nonna, che è molto premurosa e gli prepara sempre un succulento pranzetto composto di N portate. L'unica pecca è che la nonna si lascia andare un po' la mano, e le ultime volte Luca è tornato a casa con l'indigestione. Questa volta ha quindi deciso di pianificare cosa mangiare e cosa no.
Dalle sue precedenti esperienze , è riuscito a stimare quanti grammi di cibo K deve mangiare al minimo affinchè la nonna si senta soddisfatta e non si offenda dell'inappetenze del nipote. Inoltre appena arrivato in casa, è riuscito a sbirciare il menù scoprendo quale peso Pi ha ciascuna portata. Aiuta Luca a trovare l'insieme di portate con peso totale minimo ma almeno K .


Sono riuscito a capire che le portate vanno inserite in un vettore;il problema è come sommare fra di loro gli elementi di questo vettore in modo tale da avere un valore e confrontarlo con K?? Aiuto per favore...

[minomic]

Ciao,
devo dire che, a parte la storiella di Luca e di sua nonna, il problema non mi sembra molto facile e assomiglia a un problema di ottimizzazione...
Una strategia molto semplice sarebbe quella di ordinare il vettore in modo crescente, cioè dal piatto con il peso minore a quello con il peso maggiore, e quindi sommare gli elementi all'inizio del vettore fino a quando non si raggiunge K. Però non mi sembra che questo metodo funzioni: consideriamo ad esempio il caso in cui K = 6 e il vettore ordinato sia
2 | 3 | 8 | 10
Allora uno partirebbe con le somme e farebbe 2+3+8=13 ma chiaramente la soluzione ottima sarebbe mangiare solo il terzo piatto con valore 8.
Quindi, ripeto, il problema non mi sembra affatto banale. Frequenti le superiori o l'università? Nell'ambito di quale corso ti è stato assegnato questo esercizio?

P.S. Magari mi è sfuggito qualcosa e il problema è molto più semplice di come l'ho inteso io...

[minomic]

Aggiungo un'altra possibile idea, che funziona per tentativi (approccio a forza bruta): si associa al vettore con i pesi un altro vettore binario, in cui 1 significa "piatto da mangiare" e 0 significa "piatto da non mangiare". Quindi si enumerano tutte le possibili combinazioni (escludendo quella con tutti 0 che significherebbe saltare il pranzo e far arrabbiare la nonna!) e per ogni soluzione trovata si calcola il peso. A questo punto è semplice: si tiene traccia del minimo valore che soddisfa il requisito di essere maggiore o uguale a K.

Non sarà la soluzione più efficiente ma funziona e, se il numero di elementi è modesto, non crea particolari problemi.

[Aleb65]

frequento le superiori-corso informatica. Un'ottima idea sarebbe il tuo ultimo post, ma per me alle prime esperienze forse è un po' difficile da realizzare... ad esempio come potrei enumerare tutte le combinazioni? grazie comunque per l'interessamento

[minomic]

Parti da un vettore del tipo
[0, 0, ..., 0, 1]
e per passare da una combinazione alla successiva applichi la seguente procedura:
* parti da destra e guardi l'ultimo elemento
* se è 0 allora lo incrementi e hai finito
* se è 1 allora lo poni a 0 e analizzi l'elemento alla sua sinistra
* ripeti finché non trovi un elemento pari a 0, che porti a 1

Ti faccio notare che questo equivale a contare in base 2:
001
010
011
100
101
...

[Aleb65]

ok.. quando invece associo al vettore reale dei pesi questo vettore binario basta uguagliare gli elementi dei 2 vettori o bisogna fare un'altra operazione? Il vettore binario deve avere lo stesso numero di elementi del vettore dei pesi giusto? E quindi dopo aver settato il vettore binario, dovrei sommare tutti gli elementi a 1 per trovare quel valore che confronterò con K?? Scusa se ti domando tutte queste cose ma vorrei capire bene per poter metterlo successivamente su carta..

[minomic]

Sì il vettore binario deve avere lo stesso numero di elementi del vettore originale. All'inizio parti con [0, 0, ..., 0, 1] cioè un vettore che ha tutti zeri tranne l'ultimo elemento, che è pari a 1. Poi di volta in volta calcoli il peso del pasto (sommando tutti gli elementi del primo vettore che corrispondono agli elementi pari a 1 nel vettore binario), poi calcoli la combinazione successiva (con la procedura di prima), calcoli la nuova somma, ecc.

[Aleb65]

Man mano sto riuscendo a capire grazie.. ora ti volevo chiedere: gli elementi del primo vettore devono essere uguagliati con quelli del vettore binario giusto? Se si devo lavorare con gli indici giusto e posso proprio scrivere elementovettportate(1)=elementovettbinario(1) in c++ ?

[minomic]

gli elementi del primo vettore devono essere uguagliati con quelli del vettore binario giusto?

No, non devono essere uguagliati: il vettore binario indica solo se i pesi dell'altro vettore (quello delle protate) sono da considerare oppure no. Faccio un esempio per chiarire meglio
vettPortate: [3, 6, 4, 8, 2]
vettBinario: [0, 1, 1, 0, 0]
In questo caso si mangiano i piatti in seconda e terza posizione, quindi la tua somma sarà

somma = vettPortate[1] + vettPortate[2];

e varrà 10.

[Aleb65]

quindi verifica se ho capito bene..
1)carico tutti e due i vettori da input (quello binario parto da 0,0..1)
2)faccio il controllo del vettore binario: parto da destra e comincio a vedere : se è 0 lo faccio diventare 1 altrimenti si fa l'inverso fin quando abbiamo analizzato tutti gli elementi del vettore
3)faccio la somma come mi hai detto degli elementi a 1 del vettore binario
4) vado a confrontare il valore ottenuto con K.
Ti volevo domandare 2 cose: come faccio a partire da destra per il controllo nel vettore binario? Devo giocare con gli indici? La somma delle portare sarà solo una o ci sarà per ogni combinazione?? Ti prego di rispondere a tutte le mie domande per favore, mi stai aiutando molto in questa parte e ti ringrazio tanto