Максимизировать потребление энергии

Это решение, использующее линейное программирование с использованием целлюлозы ( https://pypi.org/project/PuLP ), которое дает мне оптимальное решение

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

. Я думаю, что лучше, чем исчерпывающее решение, написанное вручную.

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

Похоже, что модификация рюкзака решит эту проблему.

давайте определим нашу таблицу dp как 4-мерный массив dp [N + 1] [A + 1] [B + 1] [C + 1]

теперь некоторая ячейка dp [n] [a] [b] [c] означает, что мы рассмотрели n магазинов, из них мы выбрали магазины для мяса, b магазины для тортов и c магазины для пиццы, и в нем хранится максимум энергии, который мы можем иметь.

Переходы также просты, из некоторого состояния dp [n] [a] [b] [c] мы можем перейти к:

• dp [n + 1] [a] [b] [c] если мы пропустим n + 1-й магазин
• dp [n + 1] [a + 1] [b] [c] если мы купим мясо в магазине n + 1
• dp [n + 1] [a] [b + 1] [c], если мы покупаем торт в магазине n + 1
• dp [n + 1] [a] [b] [c + 1], если мы купить пиццу в магазине n + 1

Осталось только заполнить дп таблицу. Пример кода:

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)