Vasdarabolás (kicsit hasonló talán, mint a hátizsák probléma???), van-e rá nem teljes kipróbálással működő módszer?

Szükségem van adott darabszámú, adott hosszúságú vasdarabra (pl. 358mm hosszúból 10 db, 550mm hosszúból 9 db, 870mm hosszúból 6 db. stb.). Ez így összesen 13,750mm (plusz a vágási veszteség). A vastelepről 6m-es szálban tudom megvenni a vasat. Ebből adódik, hogy nekem ehhez legalább 3 darab szálat meg kell vegyek, akárhogyan is darabolom. Ennek eredménye lesz, hogy a végén összesen marad kb. 4250mm vasam /amit asszonynak valahogy meg kell magyarázni, hogy az még jó lesz valamire/.

Idáig a probléma egyszerű, mert néhány szorzás és néhány összeadással megvan. És ehhez még számítógép sem kell. A vasat meg is rendeltem már a vastelepről.

Olyan megoldást keresnék, hogy megadom a programnak, hogy milyen hosszúságú darabból, hány darabra van szükségem, hogy hány darab milyen hosszú vasat vettem a vastelepen /esetleg korábbról maradt még valami vasam/, és milyen széles a vágókorong /mennyi a vágási veszteség/. És akkor a programnak ki kéne "számolnia", hogy hogyan a legoptimálisabb felvágni a vasakat. Akkor optimális egy vágás ha a végén megmaradó darabok a leghosszabbak (egyenként), ha egy megmaradó darab rövidebb mint egy megadott hossz akkor azt vegye úgy, hogy nincs maradék (pl. azt mondom, hogy ami 30mm-től rövidebb azt vegye úgy, hogy sikerült elhasználni az egész szálat és nincs maradék). És pl. írja ki a képernyőre a három "legjobb" vágási elrendezést.

A programozás részét meg tudom oldani, de nem találtam jobb algoritmust mint a teljes kipróbálást, és már közel 1,5 órája számolom, hogy hogyan vágjam fel a vasaimat (most egy kispolcot akarok csinálni a sufniba, de később lesz még kis kerti asztal, meg kerti grill, meg kapuhoz is lesz ez a probléma). Ezért jutott eszembe, hogy ha lenne ilyen program, vagy legalább eljárás nem kéne kézzel számolgatni és tologatni "gondolatban" a vasakat, hogy hogyan daraboljam fel, ha már félig programozó vagyok, erre a problémára való a számítógép. De nem találtam ilyen algoritmust (igaz nem ez a szakterületem, de láttam már programot, mikrokontrollereket programozok, és ott az ilyen algoritmusok elég ritkák), és ha csak egyszer kéne nem írnék rá programoit, de most a nyáron elég sok vasat kell daraboljak, és lusta vagyok.