NxM List Combination Closest to Target

Question

Given a list of N lists, each containing M positive integers, and a separate list of M positive integers (target values), return a list of N scalars (integers with a value of 0 or more) that correspond to each list in the lists of lists, such that when each value in a list is multiplied by it's scalar, and the values at each index of each list are added together to make one final summed list, the sum of the absolute difference between each value in the summed list and the target list is minimized. If there are multiple possible outputs of equal absolute difference for a given input, output any single answer.

The solution with the fastest algorithm (by running time complexity) wins.

Examples:

Input: 
    Lists:  [[1,2], [2,1]]
    Target: [9,9]

Output:
    [3, 3]

---------- ---------- ----------


Input:
    Lists:  [[3,9,2,1], [7,1,2,3], [2,3,8,1]]
    Target: [60, 70, 50, 60]

Output:
    [6, 5, 4]

---------- ---------- ----------

Input:
    Lists:  [[9, 7, 8], [9, 4, 12]]
    Target: [176, 68, 143]

Output:
    [6, 8]

Example of Answer Corectness Checking:

Input:
        Lists:  [[9, 7, 8], [9, 4, 12]]
        Target: [176, 68, 143]
        
Output:
    [6, 8]

6 * [9, 7, 8]  = [54, 42, 48]
8 * [9, 4, 12] = [72, 32, 96]

[54, 42, 48] + [72, 42, 96] = [126, 84, 144]

summed difference:
    abs(176 - 126) + abs(68 - 84) + abs(143 - 144)
    = 50 + 16 + 1
    = 67 
    (minimize this number)

Answer 1

Python 3, Brute Force Solution

from itertools import product
import numpy as np


def abs_difference(totals, target):
    distance = sum(abs(totals - target))
    return distance


def best_combo(array, target):

    # setup, using numpy arrays for optimization
    array = np.array(array)
    target = np.array(target)
    low_difference = sum(target)
    low_combo = None
    n = len(array)

    # figure a limiting scalar for each list
    # aka, the scalar just before a scaled list gets further from the target
    individual_limits = []
    for row in array:
        row_low_difference = sum(target)
        i = 0
        while True:
            i += 1
            totals = i * row
            if abs_difference(totals, target) > row_low_difference:
                break
        individual_limits.append(i)

    # create a range for each limiting scalars
    # and create a generator function for all combinations of the value in these ranges
    # aka combinations of scalars to be multiplied by each row
    ranges = (range(i) for i in individual_limits)
    combos = product(*ranges)

    # iterate over these combos
    # figure out which combination of the rows gets closest to the target
    for combo in combos:
        totals = sum(array * np.array(combo).reshape(n, 1))
        difference = abs_difference(totals, target)
        if difference < low_difference:
            low_combo = combo
            low_difference = difference

    return low_combo


assert best_combo([[1, 2], [2, 1]], [9, 9]) == (3, 3)
assert best_combo([[3, 9, 2, 1], [7, 1, 2, 3], [2, 3, 8, 1]], [60, 70, 50, 60]) == (6, 5, 4)
assert best_combo([[9, 7, 8], [9, 4, 12]], [176, 68, 143]) == (6, 8)

Answer 2

Haskell, O(product target)

import Data.List
import Data.Ord

instance Num a=>Num[a]where
 (+)=zipWith(+)
 (-)=zipWith(-)
 (*)=zipWith(*)
 fromInteger=repeat.fromInteger
 abs=map abs
 signum=map signum

closest target vectors=
 minimumBy(comparing$sum.abs.(target-).sum.(vectors*).map fromInteger)$
 sequence$map(enumFromTo 0.succ.maximum.zipWith div target)vectors

Try it online!