Python实现：找出正整数列表中和≤目标值的所有最大子集

问题描述 #

给定一个正整数列表和目标值t，需要将列表中的所有元素划分成若干子集，满足以下要求：

• 每个子集的元素之和 ≤ t；
• 每个元素在子集中的出现次数不超过其在原列表中的出现次数；
• 优先划分出元素数量最多的子集（而非元素和最大的子集），最终输出所有划分后的子集。

示例 #

输入列表：[1, 3, 5, 2, 2, 5, 3, 1]，目标值target = 6
合法输出示例：

• [[1,2,2,1], [3, 3], [5], [5]]
• [[1,2,3], [1,2,3], [5], [5]]
  存在其他符合要求的输出形式。

贪心实现思路 #

要优先得到元素数量最多的子集，核心是每次优先选择最小的可用元素（小元素能在不超过目标值的前提下放入更多数量），直到无法再添加任何元素而不超过目标值，再开始下一个子集的构建。具体步骤：

1. 统计原列表中每个元素的剩余可用次数；
2. 循环构建子集，直到所有元素都被分配：
   • 初始化当前子集为空，当前子集和为0；
   • 从小到大遍历可用元素，尽可能多地将当前元素加入子集（每次加一个，检查是否超过目标值）；
   • 更新元素的剩余可用次数，移除已用完的元素；
   • 将当前子集加入结果列表。

Python 实现代码 #

from collections import Counter

def max_element_subsets(nums, target):
    # 统计每个元素的剩余数量
    count = Counter(nums)
    result = []
    
    while count:
        current_sum = 0
        current_subset = []
        # 每次从小到大遍历元素，优先选小元素保证数量最多
        sorted_elements = sorted(count.keys())
        
        for num in sorted_elements:
            # 只要当前元素还能用，且加入后不超过目标值，就继续加
            while count[num] > 0 and current_sum + num <= target:
                current_subset.append(num)
                current_sum += num
                count[num] -= 1
                # 如果元素用完了，从计数器中移除
                if count[num] == 0:
                    del count[num]
                    # 字典被修改后重新排序，避免遍历到已删除的元素
                    sorted_elements = sorted(count.keys())
        # 将当前子集加入结果
        result.append(current_subset)
    
    return result

# 测试示例
nums = [1, 3, 5, 2, 2, 5, 3, 1]
target = 6
print(max_element_subsets(nums, target))

代码说明 #

• 使用Counter跟踪每个元素的剩余可用次数，方便动态更新；
• 每次构建子集时从小到大遍历元素，确保能放入最多数量的元素；
• 每次添加元素后检查是否超过目标值，同时更新剩余计数，用完的元素直接从计数器中删除；
• 循环直到所有元素都被分配到子集中。

内容的提问来源于stack exchange，提问作者user1717931