找到整数输出的整数输入数组的非负整数权重，最小化权重之和

Question

问题：给定一个整数数组

inputs

和一个整数

output

，返回一个非负整数数组

weights

，使得

inputs

和

weights

的逐元素乘积之和等于

output 

且

weights

中的元素之和最小化。如果不存在解，则返回

null

（或等效值）。

输入和输出示例：

• calculateWeights([2, 4, 0, 6], 24)

  输出

  [0, 0, 0, 4]

  。

• calculateWeights([-6, -3, 5], -17)

  输出

  [4, 1, 2]

  。

• calculateWeights([-5, -3, 4, 6], 35)

  输出

  [0, 1, 2, 5]

  或

  [1, 0, 1, 6]

  。

• calculateWeights([-5, -3, 0], 10)

  输出

  null

  。

• calculateWeights([2, 4, 6], 15)

  输出

  null

  。

我正在寻找针对此类问题的最佳时间复杂度的解决方案。如果无法确定这一点，那么我真的很感激一种时间复杂度比下面的暴力方法要好得多的方法，据我所知，这种方法似乎有效。请随意使用任何适合您的语言或伪代码。

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

如果有助于找到更好的解决方案，您可以假设整数存在最小值和最大值。如果有助于找到更好的解决方案，您还可以假设此类边界是常见的

-2147483648

到

2147483647

。

Answer 1

“最佳情况时间复杂度”有点可疑，但标准 LP 就足够了：

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 时间复杂度有点复杂。