Algorytm do oszacowania ilości elementów na płaszczyźnie w jednym kierunku.

0

Witam serdecznie,

Mam taki niewielki problem. Otóż poszukuję rozwiązania problemu układania elementów na płaszczyźnie tak by w jak najefektywniejszy sposób się tam zmieściły.

Konkretnie chciałbym aby algorytm dawał poprawne rezultaty dla trzech testowych scenariuszy:

  1. Mając pewną długość x = 2200 (załóżmy jednostkę mm) oraz mając dwie możliwości do wybrania (można to sobie wyobrazić jako np długości desek) 500mm i 610mm, należy wyliczyć ich ilości w jak najefektywniejszy sposób. Rozwiązaniem powinno być tutaj 2x 500mm i 2x 600mm.

  2. Długość 2300, rozwiązanie 3x 500mm i 2x 600mm (pozostałą resztę pokrywam z krótszej długości).

  3. Długość 2750mm, rozwiązanie 2x 500 i 3x600mm (pozostałą resztę pokrywam z krótszej długości).

Czy ktoś ma może na myśli jakiś algorytm, równanie, które mogłoby to rozwiązać? Ewentualnie jakiś pomysł?

2

Lekcja na dziś: problem plecakowy dyskretny. Ale u ciebie nawet prościej, bo rozumiem że obojętne ci która deseczka? To problem wydawania reszty się nada. Twoja długość to kwota do wydania a wymiary deseczek to nominały. https://pl.wikipedia.org/wiki/Problem_wydawania_reszty#Algorytm_z_wykorzystaniem_programowania_dynamicznego

0

Dziwnie to opisane, czemu dla 2300 takie rozwiazanie? Nie powinno byc 3 * 600 + 500?

0
Shalom napisał(a):

Lekcja na dziś: problem plecakowy dyskretny. Ale u ciebie nawet prościej, bo rozumiem że obojętne ci która deseczka? To problem wydawania reszty się nada. Twoja długość to kwota do wydania a wymiary deseczek to nominały. https://pl.wikipedia.org/wiki/Problem_wydawania_reszty#Algorytm_z_wykorzystaniem_programowania_dynamicznego

No właśnie nie do końca obojętnie mi która deseczka. W algorytmie plecakowym są wagi, ja tych wag nie mam.
Chyba najłatwiej będzie mi zastosować algorytm reszty, czyli tak na prawdę chce sprawdzić czy istnieje kombinacja dla której możliwe jest uniknięcie cięcia. Później natomiast kombinacja gdzie reszta (czyli to co pozostanie do ucięcia) jest najmniejsza.

lion137 napisał(a):

Dziwnie to opisane, czemu dla 2300 takie rozwiazanie? Nie powinno byc 3 * 600 + 500?

Fakt tutaj coś pomyliłem. Natomiast chodziło mi bardziej o to, że wybierana jest kombinacja najbliżej dokładnego wyniku a cięcie jest robione na najmniejszy możliwy wymiar.

0

Rozwiązałem to w sposób bardziej intuicyjny.
Otóż dzięki temu, że mam określony zakres długości mając dwie możliwości wygenerowałem sobie jakby wszystkie kombinacje. Dzięki temu, że było ich zaledwie 110 to myślę, że jest to najoptymalniejsze rozwiązanie. Każdy rekord ma łączną długość i konfigurację ile długości 1 i długości 2.

Następnie tablicę sortuje względem długości i w razie potrzeby wyszukuje sobie pierwszy rekord, który jest większy bądź równy temu, który jest zadany.

Dzięki za podpowiedzi bo dużo mi to pomogło.
Pozdrawiam

1 użytkowników online, w tym zalogowanych: 0, gości: 1