Funkcja rekurencyjna

0

Witam,

Postaram się w miarę jasno opisać problem którego rozwiązania poszukuję. Otóż robię zakupy w sklepie, mam wózek z artykułami po określonych cenach (już zapłacone) oraz w sklepie na półkach pozostały jeszcze artykuły (również każdy ma cenę). Posiadam w portfelu określoną ilość gotówki. Zadaniem moim jest tak pozamieniać artykuły żeby w portfelu zostało mi jak najmniej pieniędzy (ewentualnie mniej niż X).

Dim Sklep As New List(Of Integer)
Dim Wozek As New List(Of Integer)
Dim Artykuly As New List(Of Integer)

Wozek.Add(1000)
Wozek.Add(500)
Wozek.Add(2711)
Wozek.Add(2476)
Wozek.Add(226)
Wozek.Add(1991)
Wozek.Add(1232)
Wozek.Add(1337)
Wozek.Add(6189)
Wozek.Add(732)
Wozek.Add(702)

Sklep.Add(702)
Sklep.Add(5240)
Sklep.Add(7220)
Sklep.Add(2000)
Sklep.Add(200)

Artykuly.AddRange(Sklep)
Artykuly.AddRange(Wozek)
Artykuly.Sort()

Dim Portfel As Integer = 2700
Portfel += Wozek.Sum

Jak widać sprzedałem wszystko do sklepu i dysponuję czystą gotówką. Próbowałem napisać funkcję rekurencyjną która za argumenty przyjmowała:

Friend Function Test(ByVal Produkty As List(Of Integer), ByVal Portfel As Integer) As Boolean

Potem była pętla For Each po Produkty i kolejne wywołanie funkcji jeśli w portfelu zostało więcej niż 100 a mniej niż 40 złotych. Jednak zwracane wyniki były nieprawidłowe. Funkcja powinna iterować dopóki nie znajdzie trafienia lub nie wyczerpie wszystkich możliwości oraz pokazać (dodać do Wynik As List(Of Integer)) które przedmioty kupiła. Po zsumowaniu wyników nijak mi się nie zgadzało. :/

Czy ma ktoś jakiś pomysł jak to rozwiązać lub chociaż naprowadzi mnie na właściwy tor? :)

Pozdrawiam,
Anthony

0

Na chwilę obecną rozwiązałem to w następujący sposób (bez rekurencji):

(...)
            Dim Prog As Integer = 100
            Dim Wynik2 As Boolean = False
            Do Until Wynik2 = True
                Dim stack As New Stack(Of Integer)
                For Each item As Integer In Artykuły
                    stack.Push(item)
                Next
                Wynik2 = Policz(stack, Portfel, Prog)
                If Wynik2 = False Then Prog += 100
            Loop
(...)
 Friend gTest As New Stack(Of Integer)
    Friend Function Policz(ByVal Produkty As Stack(Of Integer), ByVal Porftel As Integer, ByVal Prog As Integer) As Boolean
        gTest = New Stack(Of Integer)
        Do While (Produkty.Count > 0)
            Dim Produkt As Integer = Produkty.Pop
            Dim Wynik As Integer = (Portfel - Produkt)
            If Wynik <= 40 Then 'Produkt jest za drogi
            ElseIf Wynik <= Prog Then 'Osiagnieto cel
                gTest.Push(Produkt)
                Clipboard.SetText(String.Join("+", gTest) & "=" & Wynik)
                Return True
            Else 'Nadal za duzo kasy
                Porftel = Wynik
                gTest.Push(Produkt)
            End If
        Loop
        Return False
    End Function

Funkcja skupuje produkty od najdroższego do najtańszego co nie jest zupełnie tym, co chciałem osiągnąć (kupno 3-ch tańszych produktów może dać mniejszy wynik końcowy niż 1 drogiego), ale musi wystarczyć. Gdyby ktoś miał jakiś pomysł (kod jest w VB.NET, ale może być też C# lub czysta teoria)- prosiłbym o wskazówki. :)

0

Dzięki wielkie, dokładnie tego potrzebowałem. :]

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