Daily fantasy lineups contain a set number of players: for example, DraftKings has 1 QB, 2 RB, 3 WR, 1 TE, 1 flex, and 1 defense. This is the perfect setup for the multiple-choice knapsack problem (see http://www.diku.dk/users/pisinger/95-1.pdf).
We will use a modified version of the dynamic programming method used to solve the regular knapsack problem in order to solve the multiple-choice knapsack problem. We deal with the problem of flex picks by solving problems with restrictions of 3 RB, 4WR, and 2 flex, respectively, and then picking the highest-scoring solution.
The code for the algorithm is as follows. The remove_dom function is an auxiliary used to remove dominated items to speed up the algorithm and return an approximation. We do not use it.
# objects is an array of items, each item has a name, weight, and price
def remove_dom(objects):
# sort objects in increasing order of weight
objects = objects[objects[:,1].argsort()]
# iterate through all pairs of objects, if there is an object i such that w_i>w_j but p_i<p_j,
# remove object i because it is dominated by object j
new_objects = np.empty([len(objects[0])])
for i in range(len(objects)):
is_dom = False
for j in range(i):
if objects[i][2] < objects[j][2]:
is_dom = True
if not is_dom:
new_objects = np.vstack((new_objects,objects[i]))
return new_objects[1:]
class Contents:
items = []
types = []
value = 0
def __init__(self, num_types):
self.types = [0 for i in range(num_types)]
def add(self, object_num, object_value, object_type):
new_contents = Contents(len(self.types))
new_contents.items = list(self.items)
new_contents.items.append(object_num)
new_contents.types = list(self.types)
new_contents.types[object_type] += 1
new_contents.value = self.value
new_contents.value += object_value
return new_contents
# objects array has form [name, weight, value, type]
# cat_indices is a list of the last indices for each category; for example, if cat_indices=[1,2],
# item 0 would be in category 0, item 1 would be in category 1, and the rest of the items would be in category 2
# cap_cap is a list of the capacity, or maximum number of items, in each category
def multi_knapsack(objects, weight_limit, cat_indices, cat_cap):
assert len(cat_indices) == len(cat_cap)
cat = len(cat_indices) # number of categories
# don't remove dominated objects; this makes it harder to exactly fulfill the salary cap
'''
split_arr = np.split(objects, cat_indices)
for i in range(len(split_arr)-1):
split_arr[i] = remove_dom(split_arr[i])
after_index = len(split_arr[i])
# update cat_indices to account for dropped items
if i==0:
cat_indices[i] = after_index
else:
cat_indices[i] = cat_indices[i-1] + after_index
new_objects = np.vstack(split_arr[:-1])
'''
new_objects = objects
max_array = [[[Contents(len(cat_cap)) for k in range(cat_cap[int(new_objects[j][3])]+1)] for i in range(weight_limit+1)] for j in range(len(new_objects))]
max_array = [[[Contents(len(cat_cap))] for i in range(weight_limit+1)]] + max_array
for i in range(len(new_objects)):
weight = int(new_objects[i][1])
value = int(new_objects[i][2])
object_type = int(new_objects[i][3])
last_same_type = False
if i != 0:
last_same_type = object_type == int(new_objects[i-1][3])
for w in range(1,weight_limit+1):
for n in range(cat_cap[object_type]+1):
if weight max_array[i][w][n].value:
max_array[i+1][w][n] = max_array[i][w-weight][n-1].add(i,value,object_type)
else:
max_array[i+1][w][n] = max_array[i][w][n]
elif n==1:
max_array[i+1][w][n] = max_array[i][w-weight][-1].add(i,value,object_type)
else:
if last_same_type:
max_array[i+1][w][n] = max_array[i][w][n]
else:
max_array[i+1][w][n] = max_array[i][w][-1]
return [new_objects[i][0] for i in max_array[len(new_objects)][weight_limit][-1].items]
fantasylearning 