Algorithm to evenly split number with factors while maximizing the lowest weight

Question

Given a number and a list of factors, what is the most efficient way to split this number into its given factors so as to maximize the minimum weight (weight is the multiple of particular factor)?

>>> number = 32
>>> given_factors = [1,2,4]
>>> evenly_split_a_number_with_factors(number, given_factors)
[6,5,4]
# note: 6*1 + 5*2 + 4*4 == 32

Another way to think of it as:

Given:
    w1*f1 + w2*f2 + ... + wN*fN = Z

Where:
    given f1,f2,f3...fN are ascending order factors of a 
    given positive number Z

Find: w1,w2,w3...wN which are corresponding factors' non-zero positive weights and
weights being approximately evenly distributed

Example

e.g. Given: a + 2b + 4c = 32, find largest together possible a,b,c
1  2  4
a  b  c
32 00 00
00 16 00
00 00 08
08 04 04
06 05 04    <- should be the outcome of this algorithm

Answer 1

Implemented @MBo answer (selecting his answer as he told me about the logic). Feel free to comment if I missed a usecase (I deliberately am not accounting for reducing the k since purpose of this function is to get maximum minimum weights for a given set of factors)

def evenly_weight_a_number_with_factors(number, factors):
    """
    Args:
        number (int): Number to evenly split using `factors`
        factors (list): list of ints

    >>> evenly_weight_a_number_with_factors(32, [1,2,4])
    6,5,4

        Given:
            w1*f1 + w2*f2 + ... + wN*fN = Z

        Where:
            given f1,f2,f3...fN are ascending order factors of a 
            given positive number Z

        Find: w1,w2,w3...wN which are corresponding factors' non-zero positive weights and
        weights being approximately evenly distributed

        Example

        e.g. Given: a + 2b + 4c = 32, find largest together possible a,b,c
        1  2  4
        a  b  c
        32 00 00
        00 16 00
        00 00 08
        08 04 04
        06 05 04    <- should be the outcome of this algorithm

    """
    log = logging.getLogger(evenly_weight_a_number_with_factors_logger_name)

    # function to return True if all numbers in `_factors` are factors of number `n`
    are_all_factors = lambda n, _factors: all(n % f == 0 for f in _factors)

    def weighted_sum(__weights, __factors):
        return sum([wt*factor for wt, factor in zip(__weights, __factors)])

    def add_variant_wt(__weights, i, _remainder_weight):
        old__weights = __weights[:]
        if _remainder_weight < factors[i]:
            log.warn('skipping  add_variant_wt _remainder_weight: {} < factor: {}'.format(_remainder_weight, factors[i]))
            return []

        variant_wt = _remainder_weight / factors[i]
        variant_wt_rem = _remainder_weight % factors[i]
        log.debug('add_variant_wt: weights, i, renainder_weight, variant_wt, remain: {}'
                  .format((__weights, i, _remainder_weight, variant_wt, variant_wt_rem)))
        if variant_wt_rem:
            __weights[i] += variant_wt
            if i + 1 >= len(factors):
                return add_variant_wt(__weights, i-1, variant_wt_rem)

            return add_variant_wt(__weights, i+1, variant_wt_rem)

        __weights[i] += variant_wt
        log.debug('add_variant_wt i: {} before: {} after: {}'.format(i, old__weights, __weights))
        return __weights


    assert list(sorted(factors)) == factors, "Given factors {} are not sorted".format(factors)
    assert are_all_factors(number, factors) == True, "All numbers in {} are not factors of number: {}".format(factors, number)

    sum_of_all_factors = sum(factors)
    largest_possible_weight = number / sum_of_all_factors
    remainder_weight = number % sum_of_all_factors

    variant_weight_sets = []
    tmp_weights = []
    for _ in factors:
        tmp_weights.append(largest_possible_weight)

    log.debug('tmp_weights: {} remainder_weight: {}'.format(tmp_weights, remainder_weight))
    for i, _ in enumerate(factors):
        _weights = add_variant_wt(tmp_weights[:], i, remainder_weight)
        if _weights:
            variant_weight_sets.append(_weights)

    weights = variant_weight_sets[-1]    # pick wt variance where largest factor gets the biggest weight
    log.debug('variant_weight_sets: {}'.format(variant_weight_sets))
    sum_weighted = weighted_sum(weights, factors)
    assert sum_weighted == number, "sum_weighted: {} != number: {}".format(sum_weighted, number)
    return weights

Result looks like:

>>> evenly_weight_a_number_with_factors(32, [1,2,4])
[4, 4, 5]
>>> evenly_weight_a_number_with_factors(32, [1,2,8])
[2, 3, 3]
>>> evenly_weight_a_number_with_factors(32, [1,2,2])
[6, 6, 7]
>>> evenly_weight_a_number_with_factors(100, [1,2,4,4,100])
[0, 0, 0, 0, 1]
>>> evenly_weight_a_number_with_factors(100, [1,2,4,4])
[10, 9, 9, 9]
>>>

Answer 2

Possible approach: good solution shoud contain some portion with equal weights.

Start with the largest possible weight Kmax = N div SumOfFactors and split the rest of number.
If spliting is not possible - decrement weight and repeat

This approach tries to make reduction of problem size - it is important for larger sum and number of summands.

For your example - good solution should look like

32 = K * (1 + 2 + 4) + Split_of_(32 - 7 * K)
Kmax = 32 div 7 = 4
Rest = 32 - 4 * 7 = 4
Varitants of splitting rest 4 into factors: 
4 = 4  gives weights 4 4 5
4 = 2+2  gives weights  4 6 4
4 = 2+1+1  gives weights 6 5 4  
4 = 1+1+1+1 gives weights 8 4 4     

The best variant for you is 2+1+1 (perhaps one with the most different factors), while I think that solution (not listed in your example) 4 4 5 is quite good too.

Case when KMax is not suitable:

 120 into (2,7,11,19)  
 sum = 39, k=3, rest = 3,  it is impossible to make 3
           k=2, rest = 42, we can make partitions:
                       42=3*2+2*7+2*11, possible solution is 5,4,4,2    
                       42=2*2+2*19, possible solution is 4,2,2,4