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.

Note: I did find a more efficient brute force solution that iterates through all combinations of weights with the sum of the elements in weights being 0, then 1, etc., all the way up to abs(output) and returns as soon as a single solution is found since we are going up by the sum of the elements in weights. I'm leaving the current code in the question, though, as it is shorter and gets the point across. Additionally, this optimized brute-force solution is still nowhere near a good time complexity. — Gigi Bayte 2
– Gigi Bayte 2, Commented Apr 29, 2024 at 15:27

Reinderien · Accepted Answer · 2024-04-30 00:50:09Z

2

"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.

answered Apr 30, 2024 at 0:50

Reinderien

16.7k9 gold badges56 silver badges92 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Gigi Bayte 2 Over a year ago

Very interesting! Something for me to look into and understand.

Collectives™ on Stack Overflow

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

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related