[C] problema algoritmo programma

[moriarty]

salve a tutti ho un problema con un programma in c
non riesco a definire un algoritmo che compia una semplice azione

questo e quello che dovrei fare

Una ditta di trasporti dispone di un certo numero di autocarri (massimo 100).
I codici degli autocarri sono elencati in ordine alfabetico in un file che in ogni riga contiene:
· il codice dell’autocarro (su tre caratteri)
· la sua portata in tonnellate
Esempio:

FRT 35
GHD 24
SWZ 12
TES 17
VCD 26

inserendo uno specifico carico devo verificare quanti camion devo utilizzare per il trasporto

esempio output

Introduci carico: 36
Autocarri utilizzati: SWZ GHD (nessun autocarro singolo è sufficiente)
Introduci carico: 20
Autocarri utilizzati: VCD (GHD non è più disponibile)
Introduci carico: 33
Autocarri utilizzati: FRT
Introduci carico: 30
La spedizione non può essere effettuata (resta solo TES)
fine programma


e questo sarebbe quello che sono riuscito a fare
l algoritmo in fondo e incompleto

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 30


typedef struct{
char sigla[3];
int portata;
}listamezzi;

int main(int argc, char *argv[])
{
listamezzi autocarro[MAX];
listamezzi selezionato;
listamezzi temp;
int carico;
int i,cont=0, scambio=1;


FILE*f1;

if(argc!=2){
printf("errore nel numero argomenti inseriri\n");
system("pause");
return -1;
}

f1=fopen(argv[1], "r");

if(f1==NULL){
printf("errore nell apertura del file\n");
system("pause");
return -1;
}

while(fscanf(f1,"%s%d",autocarro[i].sigla,autocarro[i].portata)!=EOF){
i++;
cont++;
}
fclose(f1);

//definisco veicoli in ordine crescente in base alla portata in base alla portata tramite algoritmo bubble sort

while(scambio) {
scambio=0;
for(i=0;i<cont;i++) {
if(autocarro[i].portata>autocarro[i+1].portata){
temp=autocarro[i];
autocarro[i]=autocarro[i+1];
autocarro[i+1]=temp;
scambio=1;
}
}
}

printf("inserisci il quantitativo di carico in tonnellate da trasportare: ");
scanf("%d", &carico);

for(i=0;i<cont;i++) {
//provo ad effettuare la spedizione con un solo autocarro
if(carico<=autocarro[i].portata) {
selezionato=autocarro[i];
printf("l autocarro disponibile e il %s con una portata di %d\n", selezionato.sigla, selezionato.portata);

/*da qui in poi non saprei come continuare
nel caso in cui il carico fosse maggiore della portata di un singolo autocarro
devo sceglierene 2 o piu..solo che la scelta dovrebbe essere opportuna(nel senso che se il carico
è 36 non posso sceglierne uno con 35 e un altro solo con una tonnellata*/





system("pause");
}

[DanieleC88]

Mi puzza tanto di programmazione dinamica (http://en.wikipedia.org/wiki/Dynamic_programming).

[moriarty]

qualcuno mi da una mano?

[oNaSsIs]

A me in realtà così a prima occhiata ricorda un problema di Ricerca Operativa risolvibile attraverso il metodo Branch and Bound, che mi è capitato di usare in problemi come quello noto del Knapsack. Nel tuo caso però dovresti minimizzare la funzione relativa al numero di camion e avere un vincolo di maggiore o uguale della capienza dei camion rispetto al peso della merce da trasportare.

[moriarty]

credo che dovrei solo cercare di rendere piu semplice questo algoritmo perche altrimenti sarebbe troppo complesso e infinito
for(i=0;i<cont;i++){
if(carico<=autocarro[i].portata){
selezionato=autocarro[i];
printf("la spedizione puo essere effettuata con autocarro %s di portata %d", selezionato.sigla,selezionato.portata);
}
else{
selezionato=autocarro[i];
residuo = carico - autocarro[i].portata;
for(j=0;j<cont<j++){
if(residuo<=autocarro[i].portata){
selezionato1=autocarro[i];
printf("la spedizione puo essere effettuata con autocarro %s e %s di portata %d e %d", selezionato.sigla,selezionato.portata,selezionato1.sigla,selezionato1.portata);
}
............................................................