100 paczek oczekuje w magazynie na transport. Każda ma unikalny numer z przedziału <1; 100>. Wagę i cenę wylicza się tak:
waga(n) = (n mod 11) + 1
cena(n) = (n mod 13) + 1
Firma ma tylko 1 ciężarówkę, która mieści 250 kg. Ile może zarobić maksymalnie podczas dostawy 1 ciężarówką?
Napisałem typowy algorytm plecakowy, ale wynik jest błędny. Nie uwzględnia takiej sytuacji, że choć paczka będzie cięższa, może przynieść większe dochody albo na odwrót. Ranking cena/waga to nie wszystko:
int porownaj(const void *a, const void *b)
{
struct towar *sa = (struct towar*) a;
struct towar *sb = (struct towar*) b;
return (int)(sb->ranking - sa->ranking);
}
void zad17()
{
int i;
int sumaCen = 0;
int sumaWag = 0;
struct towar towary[100];
for(i=0; i<100; i++)
{
towary[i].n = i+1;
towary[i].waga = (i+1) % 11 + 1;
towary[i].cena = (i+1) % 13 + 1;
towary[i].ranking = towary[i].cena / towary[i].waga;
}
qsort(towary, 100, sizeof(struct towar), porownaj);
for(i=0; i<100; i++)
{
if(sumaWag + towary[i].waga > 250)
{
break; //więcej nie zmieści się do ciężarówki
}
else
{
sumaWag += towary[i].waga;
sumaCen += towary[i].cena;
}
}
printf("Maksymalna ilosc Euro: %d\n\n", sumaCen);
}
Wyliczać wszystkie kombinacje? Będzie potrzebna rekurencja albo dobrze napisany algorytm iteracyjny.