Podział na podzbiory

shamway · Post autor: **shamway** » 29 wrz 2010, o 21:45

Witam.
Porszę sobie wyobrazić taką sytuację.
Potrzebne jest mi kilka lub kilkanaście odcinków, załużmy że są to pręty stalowe. Każdy z nich ma określoną długość, każdy może mieć inna długość. Potrzebuję je wyciąć z kilku dłuższych prętów.
np mam 5 odcinków o długości 3m. a potrzebuję kilka o różnych długościach od 20 cm do 1.5.
Jak to podzielić, żeby mieć najmniej odpadów? jak dla mnie to coś koło jakichś permutacji ale żaden ze mnie matematyk, więc chciałbym prosić o pomoc. Jak do tego wogóle podejść?
Pozdrawiam.

Konikov · Post autor: **Konikov** » 29 wrz 2010, o 22:06

To zadanie z algorytmiki, problem plecakowy ;]

shamway · Post autor: **shamway** » 29 wrz 2010, o 22:25

Rewelka. teraz to jestem w domu. nawet z moim małym rozumkiem. wielkie dzięki.

Konikov · Post autor: **Konikov** » 29 wrz 2010, o 23:06

Proszę bardzo. Dla realnych problemów, gdy nie masz wklepanego programu, można jeden z algorytmów przeprowadzić na kartce ;]