时间戳

首页 > 解决方案 > 用python解决一道数学题：求和一个尽可能接近的值

python - 用python解决一道数学题：求和一个尽可能接近的值

问题描述

我有一个数字列表。现在如果我设置一个固定值V，python是否可以将列表分成几组，使得每组的总和不小于V（尽可能多地获得这些组）？

例如：如果列表是 [1,2,3,4,5] 并且 V 是 6，那么结果应该是 [[1,5],[2,3,4]]。分组意味着您不能多次使用相同的原始项目。

每个子列表可以包含多少个项目没有限制，并且数字也不是按顺序排列的（可以是一些随机数）。有人可以帮我吗？到目前为止，我的解决方案是总结所有组合并比较总和。但我很确定应该有更有效的解决方案。谢谢！

我的解决方案：我有点先使用它，然后在我的脑海中完成剩下的工作，所以它不值得进一步开发。

import itertools
import math

stuff = list(range(10))
v = 6

for L in range(0, len(stuff)+1):
    for subset in itertools.combinations(stuff, L):
        if math.fsum(subset) > v: 
            print(subset,math.fsum(subset))

标签： pythonlistmathsum

解决方案

我的解决方案具有 O(n^2) 时间复杂度。您可以按升序对列表进行排序。然后从末尾迭代列表。由于您想要最大数量的子集，然后每个大于 V 的值都添加到数组中。在其他情况下，从左右角收集值，同时实现子集之和等于 V：

def get_value_in_dict(d):
    return d.get(list(d)[0])

# Implementation for a list of dictionaries like [{'apple':1},{'pear':22},{'hat':23},{'glass':44}]
def sum_up_to_value(stuff, val):
    new_stuff = []
    sorted_stuff = list(sorted(stuff, key=lambda el: get_value_in_dict(el)))
    n = len(stuff)
    pointer_r = n - 1
    pointer_l = 0
    queue = list()

    while pointer_r >= pointer_l:
        if get_value_in_dict(sorted_stuff[pointer_r]) >= val:
            new_stuff.append([sorted_stuff[pointer_r]])
        else:
            subsum = get_value_in_dict(sorted_stuff[pointer_r])
            substuff = []
            while pointer_l < pointer_r and subsum < val:
                # get from queue
                while len(queue) and subsum < val:
                    temp = queue.pop(0)
                    subsum += get_value_in_dict(temp)
                    substuff.append(temp)
                # get from input
                else:
                    if subsum < val:
                        subsum += get_value_in_dict(sorted_stuff[pointer_l])
                        substuff.append(sorted_stuff[pointer_l])
                        pointer_l += 1
            substuff.append(sorted_stuff[pointer_r])
            # returns back smallest elements
            while subsum - get_value_in_dict(substuff[0]) >= val:
                temp = substuff.pop(0)
                queue.append(temp)
                subsum -= get_value_in_dict(substuff[0])

            if subsum < val:
                # add substuff to last element of new_stuff
                temp = new_stuff.pop()
                new_stuff.append(temp + substuff)
            else:
                new_stuff.append(substuff)
        pointer_r -= 1
    return new_stuff  # list(map(lambda el: sorted(el, key=lambda el_d: get_value_in_dict(el_d)), new_stuff)) for sorted by value elements in resulting list

推荐阅读