ну после всех выяснений выходит что у вас действительно задача про n рюкзаков. Тогда как уже заметили
- это действительно np-полная задача со всеми вытекающими проблемами и подходами к решению. Ну и я уже писал что с использованием MIP солвера оно решается буквально в пару строчек (без использования - писать кода прийдется заметно больше). Вот тут
https://python-mip.readthedocs.io/_/downloads/en/l... даже есть пример для решения рюкзака, его надо просто расширить с условием что рюкзаков много и нужно строгое совпадение.
зы: может оказатся что данных сильно много и подход с использованием MIP "в лоб" будет работать сильно медленно. В таком случае уже можно будет думать и комбинировать разные подходы.
зыы: питоновский код чисто для примера, обертки для cbc (
https://github.com/coin-or/Cbc) есть уже наверно для всех языков где это может понадобится, потому менятся будет только синтаксис. под капотом там одни фиг будет плюсовая либа
на вид должно выйти что-то такое
from typing import List
from mip import Model, minimize, xsum, BINARY
def solve(input_values: List[int], target_values: List[int]):
model = Model("m")
bin_input_is_used_to_build_target = {}
for index in range(0, len(input_values)):
bin_input_is_used_to_build_target[index] = [model.add_var(var_type=BINARY) for _ in target_values]
model.objective = minimize(
xsum(
bin_input_is_used_to_build_target[input_index][target_index] * input_values[input_index]
for input_index in range(0, len(input_values))
for target_index in range(0, len(target_values)))
)
for target_index in range(0, len(target_values)):
model += xsum(bin_input_is_used_to_build_target[input_index][target_index] * input_values[input_index]
for input_index in range(0, len(input_values))) == target_values[target_index]
for input_index in range(0, len(input_values)):
model += xsum(bin_input_is_used_to_build_target[input_index][target_index] * input_values[input_index]
for target_index in range(0, len(target_values))) <= input_values[input_index]
model.optimize()
result = {}
for target_index in range(0, len(target_values)):
result[target_index] = [input_values[input_index]
for input_index in range(0, len(input_values))
if bin_input_is_used_to_build_target[input_index][target_index].x >= 0.99]
return result
if __name__ == "__main__":
input_values = [1, 2, 1, 1, 1, 1, 3, 2, 5]
target_values= [3, 4, 5, 5]
result = solve(input_values, target_values)
for i in range(0, len(result)):
print(target_values[i], " : ", result[i])
# 3: [2, 1]
# 4: [1, 1, 2]
# 5: [5]
# 5: [1, 1, 3]
Простой
