[C] Esercitazione ostica

[elect]

Allora l'esercizio in questione è questo


Una società sportiva deve organizzare un programma di allenamento per il potenziamento delle
prestazioni fisiche dei propri atleti. Il programma prevede 4 fasi di allenamento e per ogni fase è
disponibile un certo numero di esercizi, ognuno dei quali caratterizzato da un determinato
dispendio energetico.
Le informazione relative agli esercizi possibili, al dispendio energetico loro associato (numero
minore o uguale a 500) ed alle fasi in cui sono impiegabili sono memorizzate sul file. Sul file per
ogni esercizio è riportata una riga, che contiene il nome dell’ esercizio (senza spazio), il dispendio
energetico associato e l’ elenco delle fasi in cui l’esercizio può essere impiegato (numeri di 1 a 4).
Esempio di file di ingresso:

addominali_alti 200 1 2
addominali_bassi 500 1 2
glutei 250 1 3
adduttori 350 1 3 4
bicipiti 200 1 2
quadricipiti 150 2 4
trapezi 300 2
dorsali 350 3 4
pettorali 300 2 3
abduttori 200 2 3
tricipiti 100 1 3 4
deltoidi 200 1 3
femorali 400 2 3 4

Scrivere un programma in C, che legge da tastiera il valore di N (numero di esercizi massimo in
ogni fase) e K (dispendio massimo di calorie in ogni fase) e che sia in grado di determinare per
ciascuna fase l’esercizio/gli esercizi da svolgere in modo tale da avvicinarsi il più possibile al
dispendio energetico massimo fissato, senza superarlo. Alla fine il programma deve stampare sul
schermo, per ognuna fase, la lista degli esercizi ed il dispendio energetico loro associato.

Esempio di soluzione (N=3, K=800)

Fase 1
addominali_alti 200
addominali_bassi 500
tricipiti 100
Fase 2
bicipiti 200
abduttori 200
femorali 400
Fase 3
glutei 250
adduttori 350
deltoidi 200
Fase 4
quadricipiti 150
trapezi 300
dorsali 350

Osservazione: lo stesso esercizio non può essere svolto in più di una fase.



Ovviamente non voglio che me lo svolgiate, ma vorrei solo un'idea di che struttura dati utilizzereste voi, anche pensando al fatto che debba utilizzare la recursione

[ramarromarrone]

una struttura possibile è questa

struct esercizio {
char *nome_esercizio;
int dispendio_energetico;
int *fasi;
};
typedef struct esercizio esercizio;

l'esercizio in sè è piuttosto banale, se non sai da che parte cominciare conviene che ti sfogli un manuale di c (linguaggio c kernighan&ritchie) perchè per risoverlo avrai bisogno di conoscere un minimo la libreria standard del c, definire altre strutture dati (bastano liste) e funzioni varie.
inoltre prima di postare una domanda inizia a farlo e se quello che hai fatto non funziona, lo posti e si cerca di aiutarti.

[ramarromarrone]

Originariamente inviato da elect

anche pensando al fatto che debba utilizzare la recursione

questo problema può essere risolto in maniera iterativa...quindi prima ti conviene cercare di risolverlo in maniera iterativa (- elegante ma + semplice) poi una volta che funziona potrai provare anche a definire una maniera ricorsiva di risolverlo.

PS: la struct esercizio non influenza il fatto che la soluzione sia ricorsiva o meno..

[elect]

Allora, si era pensato ad una lista di liste oppure ad un albero,

Nell'albero con sentinella, la cosa difficile è costruirlo, deve essere profondo N, poi la determinazione del cammino più pesante è facile

Stessa cosa per la lista, bisognerebbe creare una recursiva che mi crei tutte le possibili liste di N elementi su un tot di elementi in totale

[elect]

Originariamente inviato da ramarromarrone

una struttura possibile è questa

struct esercizio {
char *nome_esercizio;
int dispendio_energetico;
int *fasi;
};
typedef struct esercizio esercizio;

Anche qui c'eran diverse idee, un vettore di dimensione 4 per le fasi? O un campo per ogni fase messo a 1 se esiste o 0 se è vuoto?

Poi, ad esempio se trovo la combinazione migliore della fase 1 e questa include gli addominali_alti devo eliminarli da tutte le altre possibili ricerche per la combinazione migliore delle altre fasi..


Un'altra struttura era quella di di non avere copie per ogni singolo esercizio (come può essere ad es per addominali_alti nell'1 e nel 2) ma fare delle liste per ogni fase utilizzando dentro ogni struct 4 puntatori, uno per fase (ad es addominali_alti avrà puntatori per la fase 1 e 2 mentre 3 e 4 saranno inizializzati a NULL

[ramarromarrone]

visto che ti piacciono le cose complicate allora perchè ,anzichè tenerti in memoria strutture dati così pesanti, non crei volta per volta uno stack(alto N) in cui provi tutte le combinazioni possibili per soddisfare la richiesta? risparmi un sacco di memoria!

[elect]

Originariamente inviato da ramarromarrone

visto che ti piacciono le cose complicate allora perchè ,anzichè tenerti in memoria strutture dati così pesanti, non crei volta per volta uno stack(alto N) in cui provi tutte le combinazioni possibili per soddisfare la richiesta? risparmi un sacco di memoria!

Non hai capito non è che mi piacciono, è che devo far così

[ramarromarrone]

Originariamente inviato da elect

Anche qui c'eran diverse idee, un vettore di dimensione 4 per le fasi? O un campo per ogni fase messo a 1 se esiste o 0 se è vuoto?

un puntatore a intero è la cosa migliore...se un certo esercizio compare in 3 fasi farai
fasi = realloc(fasi, 3 * sizeof(int)); e lo riempi..

Poi, ad esempio se trovo la combinazione migliore della fase 1 e questa include gli addominali_alti devo eliminarli da tutte le altre possibili ricerche per la combinazione migliore delle altre fasi..

questo non ho capito cosa vuoi dire...

Un'altra struttura era quella di di non avere copie per ogni singolo esercizio (come può essere ad es per addominali_alti nell'1 e nel 2) ma fare delle liste per ogni fase utilizzando dentro ogni struct 4 puntatori, uno per fase (ad es addominali_alti avrà puntatori per la fase 1 e 2 mentre 3 e 4 saranno inizializzati a NULL

non ti serve fare liste per ogni fase...ogni volta controlli se l'esercizio può essere incluso nella fase corrente...così non avrai duplicati o strutture superflue..

[ramarromarrone]

Originariamente inviato da elect

Non hai capito non è che mi piacciono, è che devo far così

viene + semplice con uno stack che non alberi o liste di liste secondo me..
poi boh dovete un pò vedere voi come preferite i miei sono solo consigli di come lo farei io

[gugoXX]

Se e' un esercizio di programmazione fallo pure in modo iterativo esaurendo tutte le possibili combinazioni.
Se invece e' un erecizio di ricerca operativa o di ottimizzazione dovresti risolverlo con il Knapsack problem, che per casi come questo, ovvero quelli binari (prendo ciascun esericizio 0 o 1 volta), ha una soluzione ottima.

[ramarromarrone]

Originariamente inviato da gugoXX

ha una soluzione ottima.

non è che sia proprio vero eh...

[gugoXX]

Originariamente inviato da ramarromarrone

non è che sia proprio vero eh...

Trova la soluzione ottima in tempo polinomiale.

[ramarromarrone]

Originariamente inviato da gugoXX

Trova la soluzione ottima in tempo polinomiale.

è un problema di natura NP-completa non sempre fornisce una soluzione ottima

cmq basta off topic sennò gli facciamo + casino che altro

[gugoXX]

Originariamente inviato da ramarromarrone

è un problema di natura NP-completa non sempre fornisce una soluzione ottima

cmq basta off topic sennò gli facciamo + casino che altro

No scusa, NP-completa non significa che non si trovi la risposta ottima, che si riesce a trovare invece quasi sempre.
Significa solo che non e' dimostrabile che si possa trovare la soluzione algoritmicamente migliore di tutte per raggiungere la risposta.

In questo caso il risultato ottimo si trova sempre. E' sufficiente provare tutte le combinazioni, che si trovano comunque in tempo finito.

Ok, basta OT.