Szukanie pierwszej możliwej kombinacji stałych liczb z wieloma warunkami

0

Cześć. Próbuję napisać algorytm który znajduję pierwszą możliwą kombinację liczb stałych. Oto opis problemu:

Załóżmy że liczby to klocki o określonych unikatowych masach, kolorach i gładkości.
Są 4 masy klocków, 1, 2, 4 i 7. Niektóre klocki mogą mieć inne kolory. Można posiadać dowolną ilość jakiegokolwiek klocka, czyli np. mogę mieć:

  • 25 czerwonych klocków o masie 7, gładkie
  • 12 czerwonych klocków o masie 1, gładkie
  • 13 niebieskich klocków o masie 7, gładkie
  • 10 czerwonych klocków o masie 1, szorstkie

Klocki organizowane są na kupkach. Tylko klocki które są identyczne mogą leżeć na tej samej kupce, ale tylko 16 klocków mieści się na jednej kupce. Czyli klocki którę posiadam wyglądają tak:

  • 25/16 kupki(czyli 1 pełna i 9/16 drugiej kupki) czerwonych klocków o masie 7, gładkie
  • 12/16 kupki(czyli 3/4 pełnej kupki) czerwonych klocków o masie 1, gładkie
  • 13/16 kupki(czyli 13/16 pełnej kupki) niebieskich klocków o masie 7, gładkie
  • 10/16 kupki(czyli 5/8 pełnej kupki) czerwonych klocków o masie 1, szorstkie

Użytkownik podaję ile klocków posiada każdego typu posiada. Podaję też liczbę która jest sumą mas klocków w kombinacji którą oblicza algorytm(ta liczba jest podzielna przez 10). Na końcu podaje jaka część kombinacji klocków składa się z jakiego typu gładkości czyli przykładowo:

  • Użytkownik podaje klocki z przykładu powyżej jako klocki które posiada.
  • Użytkownik podaje liczbę 30, czyli suma mas klocków musi wynosić 30.
  • Użytkownik podaje że kombinacja musi składać się w 20% do 40% z szorstkich klocków i 60% do 80% z gładkich klocków.

Kombinacja musi spełniać jeszcze jeden warunek:

  • Musi mieścić sie na 4 kupkach

Oczywiście może się zdażyć że taka kombinacja nie instnieje.

Oto opis algorytmu. Napisałem już coś podobnego, ale klocki miały tylko masy i gładkości, do tego kombinacja nie musiała mieścić się na 4 kupkach a koncentracja materiałów była dokładnie określona. Już od tygodnia męczę się ze znalezieniem jakiegokolwiek logicznego sposobu na znalezienie prawidłowej kombinacji ale bez skutku. Niestety nie studjuję informayki gdzie na pewno nauczyłbym się zwinnych sposobów na rozwiązanie takich problemów. Dlatego pomyślałem że może ktoś podopowie mi jak to zrobić lub poda mi jakieś linki które mogą pomóc(nazwy podobnych algorytmów, lub sposoby na tworzenie tego typu rzeczy, bo ja nie wiem nawet co napisać na google żeby nie spędzić miesięcy na szukaniu odpowiednich artykułów).

0

Wygląda to na klasyczny problem z zakresu Constraint Programming. Musisz to sam klepać czy mozesz użyć języka / biblioteki która implementuje algorytmy rozwiązywania takich problemów?
Popatrz na przykład na to:
http://mozart.github.io/mozart-v1/doc-1.4.0/fdt/node15.html#section.problem.money
http://mozart.github.io/mozart-v1/doc-1.4.0/fdt/node19.html#section.problem.safe

0

Biblioteki są okej, ale na początku chciałbym spróbować sam. Nie za dużo rozumiem z tego kodu, nie znam Oz, ale dzięki za dziedzinę, poszperam trochę.

Zastanawiam się też czy nie łatwiej by było po prostu bruteforcować, Liczba którą użytkownik podaje nie może być za duża przez jedno z ograniczeń których nie wymieniłem.

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