Write a function that meets the specifications below:
def find_combination(choices, total): """ choices: a non-empty list of ints total: a positive int Returns result, a array of length len(choices) such that * each element of result is 0 or 1 * sum(result*choices) == total * sum(result) is as small as possible In case of ties, returns any result that works. If there is no result that gives the exact total, pick the one that gives sum(result*choices) closest to total without going over. """
My solution uses a brute force approach, but it is very slow. How can I implement a faster solution?
import itertools import numpy as np def find_combination(choices, total): bins = np.array(list(itertools.product([0, 1], repeat=len(choices)))) combinations = [b for b in bins if sum(choices * b) == total] return (min(combinations, key=sum) if combinations else max([b for b in bins if sum(choices * b) < total], key=sum))