Maximizar el consumo de energía

Hay tres tipos de alimentos que se proporcionan, es decir, carnes, pasteles y pizzas, y N tiendas diferentes que venden, donde solo puedo elegir un tipo de comida de cada tienda . Además, solo puedo comprar artículos en los números A, B y C, donde ‘A’ significa Carne del número total ‘A’ de tiendas diferentes (ver ejemplo). Mi tarea es consumir alimentos, para que pueda tener la máxima cantidad de energía. ejemplo,

10 <= number of stores 
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.
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

Así que para maximizar mi energía, puedo consumir …

  1. Carne de los números de la tienda:

     [1, 4, 7, 8, 9] => [56, 91, 55, 63, 81] 
  2. Pastel de números de tienda:

     [3, 5, 10] => [98, 94, 95] 
  3. Pizza de los números de la tienda:

       [2, 6] => [45, 80] 

    Esto me lleva a obtener eventualmente un nivel máximo de energía de 758.


    Como soy nuevo en la progtwigción dinámica, traté de resolverlo generando combinaciones únicas como,

    10 C 5 * (10-5) C 3 * (10-5-3) C 2 = 2520

    Aquí está mi código,

     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) 

    Sé que esta no es la manera correcta de hacerlo. ¿Cómo puedo optimizarlo?

    Esta es una solución que utiliza la progtwigción lineal a través de pulpa ( https://pypi.org/project/PuLP ) que me da la solución óptima.

     Maximum energy level: 758.0 Mapping of stores per foodtype: {1: [9, 2, 4], 0: [3, 8, 0, 6, 7], 2: [1, 5]} 

    El rendimiento debería ser mejor que un solucionador exhaustivo codificado a mano, creo.

     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)}") 

    Parece que una modificación de la mochila lo resolvería.

    definamos nuestra tabla dp como matriz de 4 dimensiones dp [N + 1] [A + 1] [B + 1] [C + 1]

    ahora, algunas células dp [n] [a] [b] [c] significa que hemos considerado n tiendas, de ellas hemos escogido una tienda de carne, b tiendas de pastelería y c tiendas de pizza y almacena la máxima energía que podemos tener.

    Las transiciones también son fáciles, desde algún estado dp [n] [a] [b] [c] podemos pasar a:

    • dp [n + 1] [a] [b] [c] si omitimos n + 1 ª tienda
    • dp [n + 1] [a + 1] [b] [c] si compramos carne de la tienda n + 1
    • dp [n + 1] [a] [b + 1] [c] si compramos pastel de la tienda n + 1
    • dp [n + 1] [a] [b] [c + 1] si compramos pizza de la tienda n + 1

    Todo lo que queda es llenar la tabla dp. Código de muestra:

     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)