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))
Improve this question
\$\endgroup\$
4
  • \$\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, 2017 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, 2017 at 6:36
  • 3
    \$\begingroup\$ The docstring and parameters names don't match. This is misleading. \$\endgroup\$
    – 301_Moved_Permanently
    Jan 19, 2017 at 7:21
  • \$\begingroup\$ Sorry, I corrected it. \$\endgroup\$
    – Tao Xu
    Jan 21, 2017 at 1:45

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.