Find nonnegative integer weights of integer inputs array for integer output, minimizing sum of weights

Question

Problem: Given an array of integers inputs and an integer output, return an array of non-negative integers weights such that the sum of the element-wise product of inputs and weights equals output and the sum of the elements in weights is minimized. Return null (or equivalent) if no solution exists.

Example inputs and outputs:

• calculateWeights([2, 4, 0, 6], 24) outputs [0, 0, 0, 4].
• calculateWeights([-6, -3, 5], -17) outputs [4, 1, 2].
• calculateWeights([-5, -3, 4, 6], 35) outputs either [0, 1, 2, 5] or [1, 0, 1, 6].
• calculateWeights([-5, -3, 0], 10) outputs null.
• calculateWeights([2, 4, 6], 15) outputs null.

I am looking for a solution with the best-case time complexity for such a problem. If this is not possible to determine, then I would really appreciate one with a significantly better time complexity than the below brute-force method, which seems to work as far as I can tell. Please feel free to use any language that is comfortable for you or pseudocode.

from itertools import product
from typing import Optional, List


def calculate_weights(inputs: List[int], output: int) -> Optional[List[int]]:
    n = len(inputs)
    
    # Generate all possible combinations of weights
    possible_weights = product(range(abs(output) + 1), repeat = n)
    
    result = None
    min_weight_sum = float("inf")
    
    for weights in possible_weights:
        # Check if the sum of the products of the inputs and weights is equal to the output and is optimal
        if sum(inputs[i] * weights[i] for i in range(n)) == output and sum(weights) < min_weight_sum:
            min_weight_sum = sum(weights)
            result = weights
    
    # Return the optimal weights if found or None otherwise
    return result

If it helps in finding a better solution, you can assume that there exists a minimum and maximum value for integers. If it helps in finding a better solution, you can additionally assume that such bounds are the common -2147483648 to 2147483647.

Answer 1

"Best-case time complexity" is a little dubious, but certainly a standard LP will suffice:

from typing import Sequence

import numpy as np
from scipy.optimize import milp, Bounds, LinearConstraint


def calculate_weights(
    inputs: Sequence[int],
    output: int,
) -> np.ndarray | None:
    n = len(inputs)

    result = milp(
        c=np.ones(n),  # minimize weights
        integrality=np.ones(shape=n, dtype=np.uint8),
        bounds=Bounds(lb=0),
        constraints=LinearConstraint(
            A=inputs, lb=output, ub=output,
        ),
    )
    if not result.success:
        return None
    return result.x


def test() -> None:
    assert np.array_equal(
        calculate_weights(inputs=(2, 4, 0, 6), output=24),
        (0, 0, 0, 4),
    )
    assert np.array_equal(
        calculate_weights(inputs=(-6, -3, 5), output=-17),
        (4, 1, 2),
    )

    weights = calculate_weights(inputs=(-5, -3, 4, 6), output=35)
    assert np.array_equal(
        weights, (0, 1, 2, 5),
    ) or np.array_equal(
        weights, (1, 0, 1, 6),
    )

    assert calculate_weights(inputs=(-5, -3, 0), output=10) is None

    assert calculate_weights(inputs=(2, 4, 6), output=15) is None


if __name__ == '__main__':
    test()

LP time complexity is a little involved.