[HELP] Algoritmai ir duom. struktūros - perrinkimo uždavinys.

Labas visiems,

Gavau ADS užduotį, kurios nesuprantu iki galo.:

Turime N darbų, kurių atlikimo trukmė t1, t2,..tN, kurių baigimo terminai d1, d2,..dN. Jei darbai

neatliekami laiku, bauda atitinkamai b1, b2,..bN. Kokia eilės tvarka atlikti darbus, kad bauda būtų

minimali.

Labai prašau jūsų visų pagalbos su šiuo perrinkimo uždaviniu. Stengiausi sugalvoti algoritmą pats, tačiau šnipštas gavosi.. Bandžiau braižytis galimus uždavinio variantus lapelyje, konsultavausi pas kai kuriuos grupiokus/kursiokus, tačiau vis tiek esu visiškai pasimetęs. Gal pradėsiu nuo konkrečių minčių: manau, kad šio uždavinio algoritme yra svarbi rekursija, kuri padėtų perrinkti visus variantus, tačiau man juos reikia optimizuoti, ir sumažinti į kuo mažesnį kiekį (remiantis logika). Gal turite minčių nuo ko pradėti? Beje, gal galėtumėte man išsamiai paaiškinti šią sąlygą? (Taip, tai gali skambėti juokingai, tačiau galbūt aš ją visiškai ne taip supratau?) Taip pat gal galėtumėte pakomentuoti, kaip programiškai galėčiau sprendimą aprašyti? (Kalba nėra svarbi, bet orientuočiausi į Java/C++/C)

Nuoširdus ačiū!

P.S nevenkite numesti ir šaltinių, iš kurių galėčiau pasiskaityti pats ir taip jūsų aiškinimas sutrumpėtų. :)

Pirma paskaičiuoji baudą, jei darbus atlieki tvarka 1, 2, 3, 4. Tada tą patį paskaičiuoji eilės tvarkai 1, 2, 4, 3. Kartoji, kol išbandysi visus galimus 4! variantų (bendru atveju N!). Išsirenki mažiausią baudą.

Eilės tvarkas turbūt patogiausia generuoti su rekursija. Jeigu programuoji C++, gali panaudoti funkciją next_permutation, kad nereikėtų rekursijos (turėtų būti kažkas panašaus ir kitose kalbose).

Dažniausiai min max uždaviniams yra taikoma Dinaminio programavimo teorija.

Gal turi kokių testų?

Nes aš salygą supratau taip jog darbai ir jų laikai yra susiję, bet tos pačios baudos gali būti rikiuojamos, taip jog būtu minimaliai. Plius jei sprendi tokius uždavinius tikrai visada stenkis

nenaudot N! algoritmo sudėtingumo

Primena kuprines užpildimo uždavinį, kuriam spręsti yra efektyvus algoritmas, manau, kad išeitų šį uždavinį suvesti iki to :)