There are three types of foods were provided i.e. meat, cake and pizza
and N different stores selling it where, i can only pick one type of food from
each store. Also I can only buy items in A, B and C numbers where 'A' means, Meat from total 'A' number of different stores (see example). My task is
to consume food, so that i can have maximum amount of energy.
example,
10 <= number of stores <br>
5 3 2 <= out of 10 stores I can pick meat from 5 stores only. Similarly,
I can pick cake from 3 out of 10 stores...
56 44 41 1 <= Energy level of meat, cake and pizza - (56, 44, 41) for first store.<br>
56 84 45 2
40 98 49 3
91 59 73 4
69 94 42 5
81 64 80 6
55 76 26 7
63 24 22 8
81 60 44 9
52 95 11 10
So to maximize my energy, I can consume...
Meat from store numbers:
[1, 4, 7, 8, 9] => [56, 91, 55, 63, 81]
Cake from store numbers:
[3, 5, 10] => [98, 94, 95]
Pizza from store numbers:
[2, 6] => [45, 80]
This leads me to eventually obtain a maximum energy level of 758.
As I am new to dynamic programming, I tried to solve it by generating unique combinations like,
10C5 * (10-5)C3 * (10-5-3)C2 = 2520
Here is my code,
nStores = 10
a, b, c = 5, 3, 2
matrix = [
[56,44,41],
[56,84,45],
[40,98,49],
[91,59,73],
[69,94,42],
[81,64,80],
[55,76,26],
[63,24,22],
[81,60,44],
[52,95,11]
]
count = a + b + c
data = []
allOverCount = [i for i in range(count)]
def genCombination(offset, depth, passedData, reductionLevel = 3):
if (depth == 0):
first = set(data)
if reductionLevel == 3:
return genCombination(0,b,[i for i in allOverCount if i not in first], reductionLevel=2)
elif reductionLevel == 2:
return genCombination(0,c,[i for i in allOverCount if i not in first], reductionLevel=1)
elif reductionLevel == 1:
xAns = 0
for i in range(len(data)):
if i < a:
xAns += matrix[data[i]][0]
elif i < a + b:
xAns += matrix[data[i]][1]
else:
xAns += matrix[data[i]][2]
return xAns
oneData = 0
for i in range(offset, len(passedData) - depth + 1 ):
data.append(passedData[i])
oneData = max(oneData, genCombination(i+1, depth-1, passedData, reductionLevel))
del data[-1]
return oneData
passedData = [i for i in range(count)]
finalOutput = genCombination(0,a,passedData)
print(finalOutput)
I know this is not the right way to do it. How can I optimize it?
This is a solution using Linear Programming through pulp (https://pypi.org/project/PuLP) that gives me the optimal solution
Maximum energy level: 758.0
Mapping of stores per foodtype: {1: [9, 2, 4], 0: [3, 8, 0, 6, 7], 2: [1, 5]}
The performance should be better than a hand-coded exhaustive solver I think.
from collections import defaultdict
import pulp
# data
nStores = 10
a, b, c = max_stores = 5, 3, 2
matrix = [
[56, 44, 41],
[56, 84, 45],
[40, 98, 49],
[91, 59, 73],
[69, 94, 42],
[81, 64, 80],
[55, 76, 26],
[63, 24, 22],
[81, 60, 44],
[52, 95, 11]
]
# create an LP problem
lp = pulp.LpProblem("maximize energy", sense=pulp.LpMaximize)
# create the list of indices for the variables
# the variables are binary variables for each combination of store and food_type
# the variable alpha[(store, food_typeà] = 1 if the food_type is taken from the store
index = {(store, food_type) for store in range(nStores) for food_type in range(3)}
alpha = pulp.LpVariable.dicts("alpha", index, lowBound=0, cat="Binary")
# add the constrain on max stores
for food_type, n_store_food_type in enumerate(max_stores):
lp += sum(alpha[(store, food_type)] for store in range(nStores)) <= n_store_food_type
# only one food type can be taken per store
for store in range(nStores):
lp += sum(alpha[(store, food_type)] for food_type in range(3)) <= 1
# add the objective to maximise
lp += sum(alpha[(store, food_type)] * matrix[store][food_type] for store, food_type in index)
# solve the problem
lp.solve()
# collect the results
stores_for_foodtype = defaultdict(list)
for (store, food_type) in index:
# check if the variable is active
if alpha[(store, food_type)].varValue:
stores_for_foodtype[food_type].append(store)
print(f"Maximum energy level: {lp.objective.value()}")
print(f"Mapping of stores per foodtype: {dict(stores_for_foodtype)}")
It looks like a modification to knapsack would solve it.
let's define our dp table as 4-dimensional array dp[N+1][A+1][B+1][C+1]
now some cell dp[n][a][b][c] means that we have considered n shops, out of them we picked a shops for meat,
b shops for cake and c shops for pizza and it stores max energy we can have.
Transitions are easy too, from some state dp[n][a][b][c] we can move to:
- dp[n+1][a][b][c] if we skip n+1 th shop
- dp[n+1][a+1][b][c] if we buy
meat from shop n+1
- dp[n+1][a][b+1][c] if we buy cake from shop n+1
- dp[n+1][a][b][c+1] if we buy pizza from shop n+1
All that's left is to fill dp table. Sample code:
N = 10
A,B,C = 5,3,2
energy = [
[56, 44, 41],
[56, 84, 45],
[40, 98, 49],
[91, 59, 73],
[69, 94, 42],
[81, 64, 80],
[55, 76, 26],
[63, 24, 22],
[81, 60, 44],
[52, 95, 11]
]
dp = {}
for n in range(N+1):
for a in range(A+1):
for b in range(B+1):
for c in range(C+1):
dp[n,a,b,c]=0
answer = 0;
for n in range(N+1):
for a in range(A+1):
for b in range(B+1):
for c in range(C+1):
#Case 1, skip n-th shop
if (n+1,a,b,c) in dp: dp[n+1,a,b,c] = max(dp[n+1,a,b,c], dp[n,a,b,c])
#Case 2, buy meat from n-th shop
if (n+1,a+1,b,c) in dp: dp[n+1,a+1,b,c] = max(dp[n+1,a+1,b,c], dp[n,a,b,c] + energy[n][0])
#Case 3, buy cake from n-th shop
if (n+1,a,b+1,c) in dp: dp[n+1,a,b+1,c] = max(dp[n+1,a,b+1,c], dp[n,a,b,c] + energy[n][1])
#Case 4, buy pizza from n-th shop
if (n+1,a,b,c+1) in dp: dp[n+1,a,b,c+1] = max(dp[n+1,a,b,c+1], dp[n,a,b,c] + energy[n][2])
answer = max(answer,dp[n,a,b,c])
print(answer)
