3
\$\begingroup\$

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))
\$\endgroup\$
  • \$\begingroup\$ Some examples here: If choices = [1,2,2,3] and total = 4 you should return either [0 1 1 0] or [1 0 0 1] If choices = [1,1,3,5,3] and total = 5 you should return [0 0 0 1 0] If choices = [1,1,1,9] and total = 4 you should return [1 1 1 0] \$\endgroup\$ – Tao Xu Jan 19 '17 at 2:56
  • 1
    \$\begingroup\$ Looks like a Subset Sum problem (see en.wikipedia.org/wiki/Subset_sum_problem). Try DP. \$\endgroup\$ – vnp Jan 19 '17 at 6:36
  • 3
    \$\begingroup\$ The docstring and parameters names don't match. This is misleading. \$\endgroup\$ – Mathias Ettinger Jan 19 '17 at 7:21
  • \$\begingroup\$ Sorry, I corrected it. \$\endgroup\$ – Tao Xu Jan 21 '17 at 1:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.