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

Odpowiedz Nowy wątek
2019-06-13 10:11
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ł?

Pozostało 580 znaków

2019-06-13 11:24
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[...]em_programowania_dynamicznego


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...
edytowany 4x, ostatnio: Shalom, 2019-06-13 11:28

Pozostało 580 znaków

2019-06-13 11:46
0

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


Raz jest 610mm, innym razem 600mm. - Delor 2019-06-13 13:50

Pozostało 580 znaków

2019-06-13 20:33
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[...]em_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.

edytowany 1x, ostatnio: Micchalek, 2019-06-13 20:46

Pozostało 580 znaków

2019-06-17 20:50
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

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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