Algorytm wybierz Player z max punktów, ale z danym koszcie

Question

Potrzebuję algorytmu, który wykonuje następujące czynności:

W fantazji ligi NBA, biorąc pod uwagę:

1. średni punkt każdego gracza całkowity
2. cena za każdego gracza
3. pułap wynagrodzeń

wybrać optymalny 9-player Line-up.

Aby użyć prostego przykładu, powiedzmy, że w lidze są tylko czterej gracze, masz pułap zarobków 10 000 $ i chcesz optymalnego (czyli maksymalnego punktu) składu 3-osobowego. Oto średnie sumy punktów i ceny:

Lebron James: 30 punktów/gra; 5000 $
Kobe Bryant: 25 punktów/gra; $ 3,500
Deron Williams: 20 punktów/gra; $ 2,500
Shelvin Mack: 15 punktów/gra; $ 2,000

Optymalnym składem byłby Bryant, Williams i Mack, który kosztowałby 8 000 $ i uzyskałby 60 punktów.

Jest jedno dodatkowe ograniczenie: program musi wybrać określoną liczbę graczy dla każdej pozycji (np. Dwóch strażników punktowych, dwóch strażników strzelających, dwóch małych napastników, dwóch napastników i jednego środka). To sprawia, że ​​projektowanie programu jest trudne.

Answer 1

używać programowania dynamicznego może rozwiązać to łatwo. patrz this

niech f[i][j] być maksymalna ilość punktów możemy uzyskać stosując j dolarów z pierwszych i graczy, więc

F [i] [j] = max {

1. f [i - 1] [j] // nie mamy wyboru i-tego graczowi
2. f [I - 1] [j - koszt [i]] + punkt [i] // wybieramy mu

}

ostatecznie f[TOTALPLAYER][MONEYCAP] jest odpowiedzią.

głównym celem jest ustalenie, czy wybrać go dla każdego gracza, czy nie.

Tablica f[][] jest właśnie używana do przyspieszenia procesu wyszukiwania.

btw, Chowlett ma rację.

Answer 2

Po pierwsze, to łatwo zauważyć, że uogólnienie problemu jest NP-Hard, i to natychmiast reduceable z Knapsack Problem:

Biorąc pod uwagę problem plecakowy: weight=W, costs_of_items=C, weight_of_items=X, zmniejszyć problem tego problemu bez ograniczeń na liczba graczy (uogólnienie będzie wynosić co najwyżej k graczy, gdzie wybrano k).

Można więc stwierdzić, że nie istnieje znane rozwiązanie problemu czasu wielomianowego.

Ale możemy opracować rozwiązanie oparte na knapsack pseudo-polynomial solution.
Dla uproszczenia, załóżmy, że mamy ograniczenie tylko w odniesieniu do liczby małych forwardów (zasady dotyczące odpowiedzi można zastosować, aby dodać więcej ograniczeń).

Następnie, problem może być rozwiązany za pomocą następującego procesu rekurencyjnego:

if i is not a forward, same as the original knapsack, while maintaining the #forwards 
    f(i,points,forwards) = max { 
       f(i-1,points-C[i],forwards) 
       f(i-1,points,forwards) 
          } 
if i is a forward: 
    f(i,points,forwards) = max { 
       //We used one of the forwards if we add this forward to the team 
       f(i-1,points-C[i],forwards-1) 
       f(i-1,points,forwards) 
          } 

bazy zostanie zerami w których jeden z wymiarów jest Zero f(0,_,_)=f(_,0,_)=0 (jak regularny plecaka) i f(_,_,-1)=-infnity (nieprawidłowy rozwiązanie)

Odpowiedź będzie następująca: f(2,W,n) (2, jeśli chodzi o liczbę przekierowań, jeśli jest ona inna, również należy ją zmienić). W to limit zarobków, a n to liczba graczy.

Rozwiązanie DP wypełni macierz reprezentującą rekursję bottom-up, aby uzyskać roztwór czasu pseudopylomialnego (Pseudo-wielomian jest tylko wtedy, gdy ograniczenia są stałe).

Po powtórzeniu procesu i dodaniu wymiaru do każdego kryterium , problem zostanie rozwiązany optymalnie za pomocą rozwiązania DP.

Złożoność dostaniesz to O(B^p * W * n) - gdzie:
B jest „czynnikiem oddział” - liczba graczy na pozycji + 1 (do zera) w przypadku B=3.
W = pułap wynagrodzeń
n = liczba graczy, aby wybrać spośród

---

Jeśli znaleźć optymalne rozwiązanie zbyt czasochłonne, bym proponuję jechać do heurystycznych rozwiązań, takich jak hill climbing lub Genetic Algorithms, który spróbuje zoptymalizować wynik tak bardzo, jak tylko może, ale nie ma gwarancji, że znajdzie globalne maksima.