Redistribution algoritmas. JAVA

Sveiki,

tokia užduotis pakliuvo ir jokių minčių.Gal kas ant kelio užves?

Įdėja - yra traukinių vagonai, vienuose kažkokie kieti daiktai sukrauti, kituose skystis. Jų maišyti negalima. Kietus galima maišyti - tarkim: akmenys, smėlis ir t.t.

Užduotis - perkrauti viską į vagonus taip, kad būtų sunaudota MAŽIAUSIAS vagonų kiekis. + Perkrauti galima tik per vieną vagoną į šonus ir negali viršyti vagono talpos ( linked list'ai naudojami ir yra žinomi visi daiktų tūriai, svoriai ir t.t. )

Turit gal kokių įdėjų, kaip mąstyti tokio tipo užduotis?

Pilnas aprašymas:

Given an existing loaded train composition, implement a function that redistributes the items loaded onto it.

After the redistribution the smallest possible number of cars should be loaded. Items can only be moved to a

neighboring car in a single step. When moving the items from one car to another all constraints should hold

(e.g. the volume of a car must not be exceeded, bulk cargo cannot be loaded onto a car that holds liquids, etc.).

Min. reikės dviejų vagonų, nes kietų ir skystų maišyti negalima. Manau, jog šitas uždavinys turėtų užvesti ant kelio: http://en.wikipedia.org/wiki/Knapsack_problem

Pirmas dalykas – susikaidyti vagonų sąrašą į trumpesnius sąrašus, kuriuose būtų vienodos konsistensijos kroviniai (t. y. paimti ir išskirti nuosekliai einančius vagonus, turinčius kietus krovinius). Tada reikės iš kiekvieno tokių sąrašų pabandyti atlaisvinti kuo daugiau vagonų – perkelti visus krovinius kiek įmanoma kairiau/dešiniau arba atlaisvinti vieną/keletą vidinių vagonų.

Jeigu pateiktum pradinių duomenų pavyzdį, būtų galima ir toliau planuoti algoritmą, nes kol kas nelabai aišku, kaip su kokiu kroviniu dirbama.

Knapstack problem pateikta gana labai atitinka vieną šio uždavinio dalį. Šiandien turėčiau test set'ą gauti. Pačiam irgi neina galvoti, kol nematau pradinių duomenų. Dėl išskaidymo vakar irgi pasižymėjau, kad pradinis punktas, bet toliau jeigu pateikti duomenys bus labai maišyti, pvz.: smulkus žvyras ir kokie nors dideli luitai, kurių tik po vieną telpa į vagoną, tada variacijų gaunasi nežmoniškai daug..

Paprasta Dinaminio Programavimo problema, kuria galima isspresti su vidutinio sudetingumo ciklu/rekurcija.