寻找输入数组的非负整数权重：使点积等于目标值且权重和最小的高效解法

问题描述 #

给定整数数组inputs和整数output，返回一个非负整数数组weights，满足inputs与weights的元素-wise乘积之和等于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

现有暴力解法 #

暴力解法通过枚举所有可能的权重组合寻找解，但时间复杂度为O((|output|+1)^n)（n为输入数组长度），仅能处理极小规模的输入：

from itertools import product
from typing import Optional, List


def calculate_weights(inputs: List[int], output: int) -> Optional[List[int]]:
    n = len(inputs)
    
    # 生成所有可能的权重组合
    possible_weights = product(range(abs(output) + 1), repeat = n)
    
    result = None
    min_weight_sum = float("inf")
    
    for weights in possible_weights:
        # 检查输入与权重的乘积和是否等于目标值，且权重和为当前最优
        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
    
    # 若找到最优权重则返回，否则返回None
    return result

需求 #

寻求该问题的最优时间复杂度解法；若无法确定最优，则需要提供时间复杂度远优于上述暴力解法的方案，可使用任意编程语言或伪代码实现。

额外假设 #

输入和输出的整数取值范围为-2147483648到2147483647。

优化解法 #

核心思路 #

将原问题拆分为两个独立的正整数组合子问题，通过动态规划（DP）求解每个子问题，再合并结果找到最小权重和的解。

问题拆分

原等式：sum(inputs[i] * weights[i]) = output，目标最小化sum(weights)。

1. 拆分输入元素：
   • 正数元素pos：x>0，贡献正乘积和
   • 负数元素：转为绝对值|x|，原等式中其贡献为-sum(|x| * w)
   • 零元素：最优解中权重必为0（不影响乘积和，且会增加权重和）
2. 转化等式：
   设M = sum(|neg_i| * w_neg_i)（非负整数），T = sum(pos_i * w_pos_i)（非负整数），则原等式变为T - M = output → T = output + M，目标转化为最小化sum(w_pos) + sum(w_neg)。

子问题求解：正整数组合的最小权重和

对于正整数数组arr和目标target≥0，用DP求解最小权重和：

• 定义dp[t]为凑出t所需的最小权重和，初始化dp[0]=0，其余为无穷大
• 对每个a∈arr，遍历t从a到target，更新dp[t] = min(dp[t], dp[t-a]+1)
• 若dp[target]仍为无穷大，说明无法凑出目标

整体算法步骤

1. 预处理输入，拆分正、负（绝对值）、零元素
2. 计算负数部分所有可凑出的M及其最小权重和（构建neg_dp字典）
3. 遍历neg_dp中的每个M，计算T=output+M：
   • 若T≥0，用DP计算正数部分凑出T的最小权重和
   • 若两者都可行，计算总权重和，记录最小值对应的权重数组
4. 单独检查仅用负数部分的情况（T=0 → M=-output，需output≤0且M可被凑出）
5. 若无可行解，返回null

代码实现（Python） #

from typing import Optional, List, Dict


def get_min_weights_and_cost(arr: List[int], target: int) -> tuple[Optional[List[int]], Optional[int]]:
    """给定正整数数组，返回凑出target的最小权重数组和对应的权重和，无法凑出则返回(None, None)"""
    if target < 0:
        return None, None
    if target == 0:
        return [0]*len(arr), 0
    
    max_t = target
    dp = [float('inf')] * (max_t + 1)
    prev = [-1] * (max_t + 1)
    dp[0] = 0
    
    for idx, a in enumerate(arr):
        for t in range(a, max_t + 1):
            if dp[t - a] + 1 < dp[t]:
                dp[t] = dp[t - a] + 1
                prev[t] = idx
    
    if dp[target] == float('inf'):
        return None, None
    
    # 回溯构建权重数组
    weights = [0]*len(arr)
    current = target
    while current > 0:
        idx = prev[current]
        weights[idx] += 1
        current -= arr[idx]
    
    return weights, dp[target]


def calculate_weights(inputs: List[int], output: int) -> Optional[List[int]]:
    pos_info = []  # (原索引, 正数)
    neg_info = []  # (原索引, 负数绝对值)
    zero_indices = []
    
    for idx, x in enumerate(inputs):
        if x > 0:
            pos_info.append((idx, x))
        elif x < 0:
            neg_info.append((idx, -x))
        else:
            zero_indices.append(idx)
    
    # 全零输入的情况
    if not pos_info and not neg_info:
        return [0]*len(inputs) if output == 0 else None
    
    # 预计算负数部分所有可凑出的M及最小权重和
    neg_dp: Dict[int, tuple[List[int], int]] = {0: ([0]*len(neg_info), 0)}
    for idx, a in enumerate(neg_info):
        new_neg_dp = neg_dp.copy()
        for m, (w, cost) in neg_dp.items():
            new_m = m + a[1]
            new_w = w.copy()
            new_w[idx] += 1
            new_cost = cost + 1
            if new_m not in new_neg_dp or new_cost < new_neg_dp[new_m][1]:
                new_neg_dp[new_m] = (new_w, new_cost)
        neg_dp = new_neg_dp
    
    min_total_cost = float('inf')
    best_weights = None
    
    # 遍历所有可能的负数组合M
    for m, (neg_w, neg_cost) in neg_dp.items():
        t = output + m
        pos_w, pos_cost = get_min_weights_and_cost([x for _, x in pos_info], t)
        if pos_w is None:
            continue
        
        total_cost = neg_cost + pos_cost
        if total_cost < min_total_cost:
            min_total_cost = total_cost
            # 构建完整权重数组
            weights = [0]*len(inputs)
            # 填充正数权重
            for (idx, _), w in zip(pos_info, pos_w):
                weights[idx] = w
            # 填充负数权重
            for (idx, _), w in zip(neg_info, neg_w):
                weights[idx] = w
            # 填充零元素权重
            for idx in zero_indices:
                weights[idx] = 0
            best_weights = weights
    
    # 检查仅用负数部分的情况（T=0 → M=-output）
    if output <= 0:
        m = -output
        if m in neg_dp:
            neg_w, neg_cost = neg_dp[m]
            if neg_cost < min_total_cost:
                weights = [0]*len(inputs)
                for (idx, _), w in zip(neg_info, neg_w):
                    weights[idx] = w
                for idx in zero_indices:
                    weights[idx] = 0
                best_weights = weights
    
    return best_weights if min_total_cost != float('inf') else None

时间复杂度分析 #

• 负数部分DP：O(n_neg * M_max)，其中M_max为最大可行M（可限制为max(0, -output) + max(pos)，避免无效计算）
• 正数部分DP：O(n_pos * T_max)，其中T_max为最大可行T（即output + M_max）
• 整体时间复杂度为O(n_neg*M_max + n_pos*T_max)，远优于暴力解法的指数级复杂度，可处理更大规模的输入。

内容的提问来源于stack exchange，提问作者Gigi Bayte 2