求数据集满足子集和≥目标值的最大组合数及Python实现优化

需求描述 #

编写函数从数据集中找出数量最多的子集组合，需满足以下规则：

• 每个子集的元素和≥目标值
• 元素一旦被归入某个子集，不可重复使用

示例说明 #

示例：
数据集 data_set = [1,2,3,4,5,6,7,8,9,10]，目标值 target_value = 5
最优分组（共8个子集）：1: [10] 2: [9] 3: [8] 4: [7] 5: [6] 6: [5] 7: [4,1] 8: [3,2]
非最优分组（仅6个子集）：1: [1,2,3] 2: [4,5] 3: [6] 4: [7] 5: [8] 6: [9]

约束条件 #

• 子集数量的理论上限为 sum(data_set)/target_value，例如数据集[5,5,5,5,5]、目标值5时，可拆分为5个单元素子集，刚好达到上限。

业务背景 #

采购商品时，每满150美元可获得一张优惠券，将订单拆分为尽可能多的、接近150美元的小单，就能获取最多优惠券，这是该算法的实际应用场景。

现有问题 #

当前提供的Python代码未充分优化，无法稳定输出最优匹配结果，寻求更完善的实现方案。

初始代码 #

from numpy import random


def get_groups(item_list=[], target=0):
    groups = []

    def recurse(current_group, remaining_item_list):
        for index in range(len(remaining_item_list)):
            if sum(current_group) + remaining_item_list[index] < target:
                current_group.append(remaining_item_list[index])
                if index+1 == len(remaining_item_list):
                    groups.append(current_group)
            else:
                current_group.append(remaining_item_list[index])
                groups.append(current_group)
                recurse([], remaining_item_list[index+1:])
                break

    item_list.sort(reverse=True)
    recurse([], item_list)

    return groups

items = [ random.randint(50) for i in range(21)]
target = 150

groups = get_groups(items, target)

print("Items: {}".format(items))

for index, group in enumerate(groups, start=1):
    print("Group {}: {}, total: {}, length: {}".format(index, group, sum(group), len(group)))

注：原代码存在缩进语法错误，已修正部分缩进问题

优化后代码 #

from numpy import random


def get_groups(item_list=[], target=0):
    groups = []

    def recurse(current_group, remaining_item_list):
        for index in range(len(remaining_item_list)):
            remaining_item_list.sort(reverse=True)
            if sum(current_group) + remaining_item_list[index] < target:
                current_group.append(remaining_item_list[index])
                if index+1 == len(remaining_item_list):
                    groups.append(current_group)
            elif sum(current_group) + remaining_item_list[index] > target and current_group:
                reverse_search(current_group, remaining_item_list)
                remaining_item_list.sort(reverse=True)
                recurse([], remaining_item_list[index:])
                break
            else:
                current_group.append(remaining_item_list[index])
                groups.append(current_group)
                recurse([], remaining_item_list[index+1:])
                break
    
    def reverse_search(current_group, remaining_item_list):
        for index in range(len(remaining_item_list)):
            remaining_item_list.sort()
            if sum(current_group) + remaining_item_list[index] < target:
                current_group.append(remaining_item_list.pop(index))
                if index+1 == len(remaining_item_list):
                    groups.append(current_group)
            else:
                current_group.append(remaining_item_list.pop(index))
                groups.append(current_group)
                current_group = []
                break


    recurse([], item_list)

    return groups

items = [ random.randint(50) for i in range(20)]
target = 150

items.sort(reverse=True)

print("Items: {}".format(items))

groups = get_groups(items, target)

for index, group in enumerate(groups, start=1):
    print("Group {}: {}, total: {}, length: {}".format(index, group, sum(group), len(group)))

内容的提问来源于stack exchange，提问作者J. Lewis