最大化消耗能源 [英] Maximize consumption Energy

问题描述

提供了三种类型的食物，即肉，蛋糕和比萨饼 和N家不同的商店出售食物，我只能从以下一种食物中选择一种 每个商店.另外，我只能以A，B和C编号购买商品，其中"A"表示从不同商店的"A"总数中购买肉类(请参见示例).我的任务是 消耗食物，以便我可以拥有最大的能量. 例如，

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...

1. 商店编号中的肉:

1. 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]

这使我最终获得了758的最大能量.

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,

₁₀ C ₅ * _(10-5) C ₃ * _{(10-5 -3)} C ₂ = 2520

₁₀C₅ * _(10-5)C₃ * _(10-5-3)C₂ = 2520

这是我的代码，

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?

推荐答案

这是通过纸浆使用线性编程的解决方案( https://pypi.org/project/PuLP )为我提供了最佳解决方案

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屋！