将值拆分为最大、最小范围内的值

Question

我想找到一种有效的算法来将整数除以最大、最小范围内的某个值。应该有尽可能少的值。

例如：最大值 = 7，最小值 = 3 然后

8 = 4 + 4
9 = 4 + 5
16 = 5 + 5 + 6 (not 4 + 4 + 4 + 4)

编辑

为了更清楚，举个例子。假设你有一堆苹果，你想把它们装进篮子里。每个篮子可以装3到7个苹果，你希望用的篮子数量越少越好。

** 前面提到了值要平分，其实不是那么重要。我比较关心篮子数量少

Answer 1

这是一个有趣的问题，让我印象深刻，所以我着手想出了一个快速的解决方案。我认为这可能是一个有趣的起点，它会为您提供一个数字尽可能少的有效解决方案，或者数字尽可能相似，所有这些都在 [=16 定义的范围内=] 和 max_bound 数字 = int(输入("Number: ")) min_bound = 3 max_bound = 7

def improve(solution):
    solution = list(reversed(solution))
    for i, num in enumerate(solution):
        if i >= 2:
            average = sum(solution[:i]) / i
            if average.is_integer():
                for x in range(i):
                    solution[x] = int(average)
                break
    return solution

def find_numbers(number, division, common_number):
    extra_number = number - common_number * division
    numbers_in_solution = [common_number] * division
    if extra_number < min_bound and \
    extra_number + common_number <= max_bound:
        numbers_in_solution[-1] += extra_number
    elif extra_number < min_bound or extra_number > max_bound:
        return None
    else:
        numbers_in_solution.append(extra_number)
    solution = improve(numbers_in_solution)
    return solution

def tst(number):
    try:
        solution = None
        for division in range(number//max_bound, number//min_bound + 1):  # Reverse the order of this for numbers as close in value to each other as possible.
            if round (number / division) in range(min_bound, max_bound + 1):
                solution = find_numbers(number, division, round(number / division))
            elif (number // division) in range(min_bound, max_bound + 1):  # Rarely required but catches edge cases
                solution = find_numbers(number, division, number // division)
            if solution:
                print(sum(solution), solution)
                break
    except ZeroDivisionError:
        print("Solution is 1, your input is less than the max_bound")

tst(number)
for x in range(1,100):
    tst(x)

这段代码只是为了演示一个想法，我相信可以对其进行调整以获得更好的性能。

将值拆分为最大、最小范围内的值

split a value into values in max, min range

math

mathematical-optimization

python-3.x