What are some good alternatives to the greedy algorithm?

Question

Algorithms

I want to split the number into a certain number of numbers, taking into account the fact that these numbers are not infinite. For example
{1: 10, 2: 30: 3:12}
When generating the number 10, Greedy will immediately pull out all the threes and 1 unit, although it would be optimal to form the number from twos since there are more of them.

* there is a pool of numbers I, there is a pool of numbers Q. And you need to compose all the numbers in Q using only what is in I (without violating the limit on the number of uses)

Answer 1

Well, after all the clarifications, it turns out that you really have a problem about n backpacks. Whereas, as already noted
, this is indeed an np-complete task with all the ensuing problems and approaches to solving it. Well, I already wrote that using the MIP solver, it can be solved in just a couple of lines (without using it, you will have to write much more code). Here https://python-mip.readthedocs.io/_/downloads/en/l... there is even an example for solving a backpack, you just need to expand it with the condition that there are a lot of backpacks and you need a strict match.
PS: it may turn out that there is a lot of data and the approach using MIP "on the forehead" will work very slowly. In this case, it will already be possible to think and combine different approaches.
PS: Python code is purely for example, wrappers for cbc (https://github.com/coin-or/Cbc) probably already exists for all languages ​​where it may be needed, so only the syntax will change. under the hood there are some figs there will be a plus one
, something like this should look like

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]

Answer 2

Your task is a Multiplicative 0-1 backpack. Here it is necessary to mention NP and other terrible words that mean that there is no good solution here. Greedy - if some approximation of the optimal answer fits. It is worth trying to collect numbers from the smallest ones, trying to put as many numbers as possible there.
Branch and bound method (actually exhaustive search with optimizations and heuristics).
You can write the problem in the form of integer linear programming and set any of the existing solvers on it. There is a good chance that this will find the optimal solution very quickly.