Najlepszy możliwy układ rabatów na produkty z listy

Cześć!

To mój pierwszy post więc proszę o wyrozumiałość! :)

Poszukując wyposażenia kuchni w trakcie remontu wpadłem na promkę w jednej ze znanych sieciówek, której wytłumaczenie jest proste. Spośród produktów znajdujących się w promocji mamy do wyboru.

Kupić drugi produkt 22% taniej
albo kupić trzeci produkt 44% taniej
albo kupić czwarty produkt 77% taniej
albo kupić piąty produkt za 1zł.

Oczywiście nie musimy wrzucać wszystkiego w jeden koszyk, ba czasem najlepiej jest go podzielić na przyklad na dwa paragony ;)

Chciałbym napisać program, który po podaniu elementów (nw, np w liście) pokaże nam jaki jest najbardziej opłacalny układ "koszyka".

Przykładowo, kupując pięć produktów na promocji

shopping_list =  [2500, 2500, 2300, 1700, 1200]

(Oczywiście elementy sortujemy wcześniej według ceny i układamy w "zestawy"). Mamy do wyboru następujące układy koszyka:

1:
2500
2500 -> 2500 * 0,78

2300
1700 -> 1700 * 0,78

1200

2:
2500
2500
2300 -> 2300 * 0,56

1700
1200 -> 1200 * 0,78

3:
2500
2500
2300
1700 -> 1700 * 0,23

1200

4:
2500
2500
2300
1700
1200 -> 1

itd. W powyższym przypadku wygrywa trzeci zestaw.

Oczywiście w przypadku na przykład czterech produktów w koszyku możliwe są kombinacje 2 x 22% rabatu, albo 1x44% rabatu (na trzeci produkt) albo 1 x 77% (na czwarty produkt). Rozpiszę jeszcze case z siedmioma produktami:

first_case = [(1, 2), (3, 4), (5, 6), 7]
# 22% discount on: 2th, 4th, 6th products

second_case = [(1, 2, 3, 4), (5, 6), 7]
# 77% discount on: 4th product, 22% discount on: 6th product

third_case = [(1, 2, 3, 4, 5), (6, 7)]
# 5th product for 1PLN, 22% discount on 7th product

fourth_case = [(1, 2, 3), (4, 5, 6), 7]
# 44% discount on 3th, 44% pn 6th product

fifth_case = [(1, 2), (3, 4, 5), (6, 7)]
# 22% discount on 2th product, 44% on 5th product, 22% on 7th product

sixth_case = [(1, 2, 3, 4), (5, 6, 7)]
# 77% discount on 4th product, 44% on 7th product

Na razie kompletnie nie mam wizji jak podejść do tego tematu. W pierwszym kroku trzeba chyba napisać jakiś mechanizm, który w zależności od ilości elementów w liście pozwoli na wygenerowanie możliwych układów. Później dla każdego układu wyliczyć rabaty i porównać który z nich daje największe korzyści. Zastanawiam się po prostu nad jakimś globalnym rozwiązaniem, które będzie niezależne od ilości elemenów. W sesnie - czy będzie ich jeden czy też sto :)

Z góry dzięki na jakieś nakierowanie!!

Najpierw bym to posortował malejąco i nie leciałbym wszystkich przypadków, tylko grupował te najdroższe (gdyby ceny były [100,90,80,70,60,50,40,30,20,10] to 10 nigdy bym nie zgrupował z 100 a maksymalnie rozpatrywałbym 50 i 10). Na najdroższy produkt i tak nie ma rabatu, więc też nie trzeba rozpatrywać czy się opłaca czy nie. Na każdy następny produkt, albo możemy wziąć rabat - i zakończyć "nabijanie na paragon" albo nie brać i rozpatrywać, czy opłaca się wziąć na następny). Żeby zoptymalizować, maksymalnie można rozpatrywać do 5 produktów na paragon. Dlatego wydaje mi się, że mniej-więcej tak mogłoby to wyglądać:

function optimizePrice(prices) {
  return helper(0, 0, 0, prices)
}

function helper(currentSum, index, nInOrder, prices) {
  if(index === prices.length - 1) {
    return applyDiscount(prices[index], nInOrder)
  }

  const minPriceWithDiscount = helper(currentSum + applyDiscount(prices[index], index + 1, 0, prices)) // 0 - bo zaczynamy "nowy paragon"
  const minPriceWithoutDiscount = helper(currentSum, index + 1, nInOrder + 1, prices) // nInOrder + 1 bo nabijamy kolejny produkt na paragon / nie wykorzystujemy rabatu jeśli nie jest to potrzebne (nie musi być potrzebne, jeżeli `nInOrder % 5 != 4`)

  return minPriceWithDiscount < minPriceWithoutDiscount? minPriceWithDiscount : minPriceWithoutDiscount
}

Nie uwzględniłem w tym 5 produktów na paragon (można to przerzucić do metody applyDiscount() i po prostu nInOrder % 5. Można byłoby też wziąć i dodać jakąś memoizację żeby cache'ować wyniki lub przejść na iteracyjną wersję w celu optymalizacji.

PS: Pewien rozwiązania nie jestem, ale wydaje mi się, że powinno zadziałać. Kod w Jsie.
PS2: Kod w obecnym stanie powinien też wziąć pod uwagę, sytuację w której wszystkie przedmioty byłyby nabijane na osobne rachunki (co oczywiście nie będzie optymalne więc taki przypadek też można jakoś wykluczyć)

Tak naprawę potrzebujesz różnych kombinacji cenowych. Najpierw grupujesz produkty po cenach (bez sensu liczyć jest telewizor i pralkę osobno jak są w tej samej cenie, chyba że ma to znaczenie w przypadku promocji). Potem generujesz wszystkie możliwe kombinacje i określając funkcję celu (najniższy rachunek) wybierasz najlepszą opcję. Jak będziesz miał dużo produktów i algorytm będzie działał za długo to musisz poszukać niedeterministycznego rozwiązania np. algorytmów genetycznych.

Fajny problem ;)

Na początku trzeba sobie uświadomić ile może być paragonów - tutaj jest łatwo bo możesz ich mieć od 1 do 5 (bo tyle mamy produktów i wszystkie musimy kupić), czyli wszystko trzeba rozłożyć na:

• jednym paragonie
• dwóch paragonach
• trzech paragonach
• czterech paragonach
• pięciu paragonach

tutaj zrozumienie jest analogiczne i łatwo się skaluje na n produktów (w przypadku 7 produktów będzie podobnie czyli min. 1 paragon, a max. siedem paragonów, itd.)

Następnie trzeba to jakoś rozłożyć na te paragony, w przypadku 1 pragonu jest łatwo - bo jest tylko jedna taka możliwość, w przypadku max. liczby paragonów też jest łatwo bo będzie też tylko jedna taka możliwość. Ale jak policzyć ile jest możliwości dla 2 paragonów?
W przypadku jeżeli mamy 5 produktów (i każdy musi być kupiony) podział może być 1-4 (jeden produkt na jednym paragonie, a reszta na drugim), albo 2-3 (dwa produkty na jednym, a trzy na drugim) oczywiście każdy taki przypadek(np. nazwijmy go 1-4) wymaga sprawdzenia ilości kombinacji (kolejność na paragonie nie ma znaczenia bo i tak będzie na końcu sortowany po cenie od najdroższego do najtańszego) czyli liczmy na paragonie 1-4 jest 5 kombinacji, a na paragonie 2-3 - jest 10 kombinacji - co razem daje nam 15 możliwych ułożeń produktów na 2 paragonach.

Dla 3 paragonów? tutaj mamy sytuacje 1-1-3 albo 1-2-2 inaczej się nie da rozłożyć 5 produktów na 3 paragonach - sumarycznie tutaj jest 15 możliwych kombinacji.
Dla 4 paragonów? tutaj jest tylko jedna możliwość 1-1-1-2 czyli kombinacji będzie 10

Więc w ogólności trzeba wygenerować wszystkie kombinacje dla każdego paragonu i potem na każdym takim paragonie nanieść funkcje zniżki - i tutaj już łatwo bo jak widzisz ze tuple ma tylko 2 elementy to aplikujesz funkcje 2 argumentową, jak 3 to 3 argumentową (argumentową mówię nie jako implementacja ale jako ilość produktów do zniżki)

Paragony od 1 do 5 mogą wyglądać tak (kolejność paragonów nie ma znaczenia bo są to niezależne płatności przy kasie):

Jeden paragon:

[[0, 1, 2, 3, 4]]

Dwa paragony:

[[0, 1, 2, 3], [4]]
[[0, 1, 2, 4], [3]]
[[0, 1, 3, 4], [2]]
[[0, 2, 3, 4], [1]]
[[0, 3, 4], [1, 2]]
[[0, 1, 4], [2, 3]]
[[0, 2, 4], [1, 3]]
[[0, 4], [1, 2, 3]]
[[0, 1, 2], [3, 4]]
[[0, 1, 3], [2, 4]]
[[0, 2, 3], [1, 4]]
[[0, 3], [1, 2, 4]]
[[0, 1], [2, 3, 4]]
[[0, 2], [1, 3, 4]]
[[0], [1, 2, 3, 4]]

Trzy paragony:

[[0, 1, 2], [3], [4]]
[[0, 1, 3], [2], [4]]
[[0, 2, 3], [1], [4]]
[[0, 3], [1, 2], [4]]
[[0, 1], [2, 3], [4]]
[[0, 2], [1, 3], [4]]
[[0], [1, 2, 3], [4]]
[[0, 1, 4], [2], [3]]
[[0, 2, 4], [1], [3]]
[[0, 4], [1, 2], [3]]
[[0, 3, 4], [1], [2]]
[[0, 4], [1, 3], [2]]
[[0, 4], [1], [2, 3]]
[[0, 1], [2, 4], [3]]
[[0, 2], [1, 4], [3]]
[[0], [1, 2, 4], [3]]
[[0, 3], [1, 4], [2]]
[[0], [1, 3, 4], [2]]
[[0], [1, 4], [2, 3]]
[[0, 1], [2], [3, 4]]
[[0, 2], [1], [3, 4]]
[[0], [1, 2], [3, 4]]
[[0, 3], [1], [2, 4]]
[[0], [1, 3], [2, 4]]
[[0], [1], [2, 3, 4]]

Cztery paragony:

[[0, 1], [2], [3], [4]]
[[0, 2], [1], [3], [4]]
[[0], [1, 2], [3], [4]]
[[0, 3], [1], [2], [4]]
[[0], [1, 3], [2], [4]]
[[0], [1], [2, 3], [4]]
[[0, 4], [1], [2], [3]]
[[0], [1, 4], [2], [3]]
[[0], [1], [2, 4], [3]]
[[0], [1], [2], [3, 4]]

Pięć paragonów:

[[0], [1], [2], [3], [4]]

Jak widzisz masz tylko 52 możliwości kupienia 5 produktów na 5 różnych ilości paragonów.

Pewnie zapytasz jak wygenerować te kombinacje. W matematyce to się nazywa liczba permutacji zbioru n-elementowego z ilościa k cykli - mówią na to liczby Stirlinga
http://student.krk.pl/024-Dudek-Krakow/other/stirlinga.html

I jak juz masz wszystkie możliwe paragony to nakładasz funkcję zniżki i patrzysz który jest najmniejszy i jedziesz do sklepu ;)