So this is a variation of the Knapsack Problem I came with the other day.
It is like a 0-1 Knapsack Problem where there are multiple groups and each item belongs to only one group. The goal is to maximize the profits subject to the constraints. In this case, a fixed number of items from each group have to be chosen for each group.
It is similar to the Multiple Choice Knapsack Problem, but in that case you only pick 1 of item of each group, in this one you want to pick x amount of items of each group
So, each item has: value, weight and group
Each group has an item count (Ex: if group A (or 0) has 2, the final solution needs to have 2 items of group A, no more no less)
And and you also have a maximum capacity (not related to the groups)
This translates into:
values[i] = The value of the ith elementweights[i] = The weigth of the ith elementgroups[i] = The group of the ith elementC = Capacityn = Amount of elementsm = Amount of groupscount[j] = Amount of items of group jI'm attempting a Recursive solution first and then I will try a Dynamic approach.
Any solution would be appreciated (preferably Python, but anything will do :) ).
Usefull links I found:
Full code also in: https://github.com/pabloroldan98/knapsack-football-formations
Explanation after the code.
This code is for an example where you have a Fantasy League with a playersDB where each player has price (weight), points (value) and position (group); there is a list of possible_formations (group variations); and a budget (W) you can't go over.
main.py:
from group_knapsack import best_full_teams
playersDB = [
Player(name="Keylor Navas", price=16, points=7.5, position="GK"),
Player(name="Laporte", price=23, points=7.2, position="DEF"),
Player(name="Modric", price=22, points=7.3, position="MID"),
Player(name="Messi", price=51, points=8.2, position="ATT"),
...
]
possible_formations = [
[3, 4, 3],
[3, 5, 2],
[4, 3, 3],
[4, 4, 2],
[4, 5, 1],
[5, 3, 2],
[5, 4, 1],
]
budget = 300
best_full_teams(playersDB, possible_formations, budget)
group_knapsack.py:
import itertools
from MCKP import knapsack_multichoice_onepick
def best_full_teams(players_list, formations, budget):
formation_score_players = []
for formation in formations:
players_points, players_prices, players_comb_indexes = players_preproc(
players_list, formation)
score, comb_result_indexes = knapsack_multichoice_onepick(
players_prices, players_points, budget)
result_indexes = []
for comb_index in comb_result_indexes:
for winning_i in players_comb_indexes[comb_index[0]][comb_index[1]]:
result_indexes.append(winning_i)
result_players = []
for res_index in result_indexes:
result_players.append(players_list[res_index])
formation_score_players.append((formation, score, result_players))
print("With formation " + str(formation) + ": " + str(score))
for best_player in result_players:
print(best_player)
print()
print()
formation_score_players_by_score = sorted(formation_score_players,
key=lambda tup: tup[1],
reverse=True)
for final_formation_score in formation_score_players_by_score:
print((final_formation_score[0], final_formation_score[1]))
return formation_score_players
def players_preproc(players_list, formation):
max_gk = 1
max_def = formation[0]
max_mid = formation[1]
max_att = formation[2]
gk_values, gk_weights, gk_indexes = generate_group(players_list, "GK")
gk_comb_values, gk_comb_weights, gk_comb_indexes = group_preproc(gk_values,
gk_weights,
gk_indexes,
max_gk)
def_values, def_weights, def_indexes = generate_group(players_list, "DEF")
def_comb_values, def_comb_weights, def_comb_indexes = group_preproc(
def_values, def_weights, def_indexes, max_def)
mid_values, mid_weights, mid_indexes = generate_group(players_list, "MID")
mid_comb_values, mid_comb_weights, mid_comb_indexes = group_preproc(
mid_values, mid_weights, mid_indexes, max_mid)
att_values, att_weights, att_indexes = generate_group(players_list, "ATT")
att_comb_values, att_comb_weights, att_comb_indexes = group_preproc(
att_values, att_weights, att_indexes, max_att)
result_comb_values = [gk_comb_values, def_comb_values, mid_comb_values,
att_comb_values]
result_comb_weights = [gk_comb_weights, def_comb_weights, mid_comb_weights,
att_comb_weights]
result_comb_indexes = [gk_comb_indexes, def_comb_indexes, mid_comb_indexes,
att_comb_indexes]
return result_comb_values, result_comb_weights, result_comb_indexes
def generate_group(full_list, group):
group_values = []
group_weights = []
group_indexes = []
for i, item in enumerate(full_list):
if item.position == group:
group_values.append(item.points)
group_weights.append(item.price)
group_indexes.append(i)
return group_values, group_weights, group_indexes
def group_preproc(group_values, group_weights, initial_indexes, r):
comb_values = list(itertools.combinations(group_values, r))
comb_weights = list(itertools.combinations(group_weights, r))
comb_indexes = list(itertools.combinations(initial_indexes, r))
group_comb_values = []
for value_combinations in comb_values:
values_added = sum(list(value_combinations))
group_comb_values.append(values_added)
group_comb_weights = []
for weight_combinations in comb_weights:
weights_added = sum(list(weight_combinations))
group_comb_weights.append(weights_added)
return group_comb_values, group_comb_weights, comb_indexes
MCKP.py:
import copy
def knapsack_multichoice_onepick(weights, values, max_weight):
if len(weights) == 0:
return 0
last_array = [-1 for _ in range(max_weight + 1)]
last_path = [[] for _ in range(max_weight + 1)]
for i in range(len(weights[0])):
if weights[0][i] < max_weight:
if last_array[weights[0][i]] < values[0][i]:
last_array[weights[0][i]] = values[0][i]
last_path[weights[0][i]] = [(0, i)]
for i in range(1, len(weights)):
current_array = [-1 for _ in range(max_weight + 1)]
current_path = [[] for _ in range(max_weight + 1)]
for j in range(len(weights[i])):
for k in range(weights[i][j], max_weight + 1):
if last_array[k - weights[i][j]] > 0:
if current_array[k] < last_array[k - weights[i][j]] + \
values[i][j]:
current_array[k] = last_array[k - weights[i][j]] + \
values[i][j]
current_path[k] = copy.deepcopy(
last_path[k - weights[i][j]])
current_path[k].append((i, j))
last_array = current_array
last_path = current_path
solution, index_path = get_onepick_solution(last_array, last_path)
return solution, index_path
def get_onepick_solution(scores, paths):
scores_paths = list(zip(scores, paths))
scores_paths_by_score = sorted(scores_paths, key=lambda tup: tup[0],
reverse=True)
return scores_paths_by_score[0][0], scores_paths_by_score[0][1]
player.py:
class Player:
def __init__(
self,
name: str,
price: float,
points: float,
position: str
):
self.name = name
self.price = price
self.points = points
self.position = position
def __str__(self):
return f"({self.name}, {self.price}, {self.points}, {self.position})"
@property
def position(self):
return self._position
@position.setter
def position(self, pos):
if pos not in ["GK", "DEF", "MID", "ATT"]:
raise ValueError("Sorry, that's not a valid position")
self._position = pos
def get_group(self):
if self.position == "GK":
group = 0
elif self.position == "DEF":
group = 1
elif self.position == "MID":
group = 2
else:
group = 3
return group
Okay,so I managed to find a solution translating what was here: Solving the Multiple Choice Knapsack Problem from C++ to Python. My solution also gives the path that got you to that solution. It uses Dynamic Programming and it's very fast.
The input data, instead of having groups[i], has the weights and the values as a list of lists, where every list inside represent the values of each group:
weights[i] = [weights_group_0, weights_group_1, ...]values[i] = [values_group_0, values_group_1, ...]Where:
weights_group_i[j] = The weigth of the jth element of the ith groupvalues_group_i[j] = The value of the jth element of the ith groupThose would be the inputs of knapsack_multichoice_onepick. Here is an example:
# Example
values = [[6, 10], [12, 2], [2, 3]]
weights = [[1, 2], [6, 2], [3, 2]]
W = 7
print(knapsack_multichoice_onepick(weights, values, W)) # (15, [(0, 1), (1, 1), (2, 1)])
After that I followed @user3386109 's suggestion and did the combinations with the indexes. The group preprocesing methods are players_preproc, generate_group and group_preproc.
Again, this code is for an example where you have a Fantasy League with a playersDB where each player has price (weight), points (value) and position (group); there is a list of possible_formations (group variations); and a budget (W) you can't go over.
The best_full_teams method prints everything and uses all the previous ones.