Вопрос: Какие есть достойные альтернативы жадному алгоритму (greedy)?

Лучший ответ:
Ваша задача - Мультипликативный 0-1 рюкзак. Тут надо упомянуть NP и другие страшные слова, которые означают, что хорошего решения тут нет. Жадность - если подойдет какая-то аппроксимация оптимального ответа. Стоит пытаться собирать числа с самых мелких, пытаясь засунуть туда как можно большие числа.
Метод ветвей и границ (фактически полный перебор с оптимизациями и эвристиками).

Можно записать задачу в виде целочисленного линейного программирования и натравить на нее любой из существующих решателей. Есть хорошие шансы, что это очень быстро найдет оптимальное решение.

Худший ответ:
ну после всех выяснений выходит что у вас действительно задача про 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]