找出数据集中的最大组合数。

huangapple
go评论100阅读模式
英文:

Find the maximum number of combinations from a data set

问题

需要编写一个函数，该函数从数据集中找到最大组合数，其中每个子集组合的总和>=目标值。一旦从数据集中取出数字并放入组合中，它们就不能在另一个组合中重复使用。例如，如果data_set = [1,2,3,4,5,6,7,8,9,10]和target_value = 5，则组合将是：

  1. 1: [10] 2: [9] 3: [8] 4: [7] 5: [6] 6: [5] 7: [4,1] 8: [3,2]

不好的分组示例将是：

  1. 1: [1,2,3] 2: [4,5] 3: [6] 4: [7] 5: [8] 6: [9]

或

  1. 1: [1,2,3] 2: [4,5] 3: [6,7,8,9]

我认为一个约束是子集的数量不能大于sum(data_set)/target_value，即如果data_set = [5,5,5,5,5]和target_value = 5，则结果应为[5],[5],[5],[5],[5]。

为了提供背景信息，我有一大堆物品需要从商店购买，商店在购买金额超过$150时会提供一张优惠券，如果你一次购买所有物品，你将只收到一张优惠券，但如果你将物品拆分成尽可能接近$150的小笔购买，你将获得尽可能多的优惠券。

以下是当前的代码，但显然不是最优化的，我在寻找更好匹配时遇到了困难：

  1. from numpy import random
  3. def get_groups(item_list=[], target=0):
  4.     groups = []
  6.     def recurse(current_group, remaining_item_list):
  7.         for index in range(len(remaining_item_list)):
  8.             if sum(current_group) + remaining_item_list[index] < target:
  9.                 current_group.append(remaining_item_list[index])
  10.                 if index + 1 == len(remaining_item_list):
  11.                     groups.append(current_group)
  12.             else:
  13.                 current_group.append(remaining_item_list[index])
  14.                 groups.append(current_group)
  15.                 recurse([], remaining_item_list[index + 1:])
  16.                 break
  18.     item_list.sort(reverse=True)
  19.     recurse([], item_list)
  21.     return groups
  23. items = [random.randint(50) for i in range(21)]
  24. target = 150
  26. groups = get_groups(items, target)
  28. print("Items: {}".format(items))
  30. for index, group in enumerate(groups, start=1):
  31.     print("Group {}: {}, total: {}, length: {}".format(index, group, sum(group), len(group)))

编辑：以下是一些更优化的代码，我相信它不是100%正确，但它更好：

  1. from numpy import random
  3. def get_groups(item_list=[], target=0):
  4.     groups = []
  6.     def recurse(current_group, remaining_item_list):
  7.         for index in range(len(remaining_item_list)):
  8.             remaining_item_list.sort(reverse=True)
  9.             if sum(current_group) + remaining_item_list[index] < target:
  10.                 current_group.append(remaining_item_list[index])
  11.                 if index + 1 == len(remaining_item_list):
  12.                     groups.append(current_group)
  13.             elif sum(current_group) + remaining_item_list[index] > target and current_group:
  14.                 reverse_search(current_group, remaining_item_list)
  15.                 remaining_item_list.sort(reverse=True)
  16.                 recurse([], remaining_item_list[index:])
  17.                 break
  18.             else:
  19.                 current_group.append(remaining_item_list[index])
  20.                 groups.append(current_group)
  21.                 recurse([], remaining_item_list[index + 1:])
  22.                 break
  23.     
  24.     def reverse_search(current_group, remaining_item_list):
  25.         for index in range(len(remaining_item_list)):
  26.             remaining_item_list.sort()
  27.             if sum(current_group) + remaining_item_list[index] < target:
  28.                 current_group.append(remaining_item_list.pop(index))
  29.                 if index + 1 == len(remaining_item_list):
  30.                     groups.append(current_group)
  31.             else:
  32.                 current_group.append(remaining_item_list.pop(index))
  33.                 groups.append(current_group)
  34.                 current_group = []
  35.                 break
  37.     recurse([], item_list)
  39.     return groups
  41. items = [random.randint(50) for i in range(20)]
  42. target = 150
  44. items.sort(reverse=True)
  46. print("Items: {}".format(items))
  48. groups = get_groups(items, target)
  50. for index, group in enumerate(groups, start=1):
  51.     print("Group {}: {}, total: {}, length: {}".format(index, group, sum(group), len(group)))
英文:

I need to write a function that finds the maximum number of combinations from a data set, where the sum of each of the subset combinations are &gt;= a target value. Once numbers are taken from the data_set and put into a combination they cannot be reused in another combination For example
data_set = [1,2,3,4,5,6,7,8,9,10] target_value = 5
the combinations would be
1: [10] 2: [9] 3: [8] 4: [7] 5: [6] 6: [5] 7: [4,1] 8: [3,2]
an example of bad grouping would be
1: [1,2,3] 2: [4,5] 3: [6] 4: [7] 5: [8] 6: [9]
or 1: [1,2,3] 2: [4,5] 3: [6,7,8,9].
I believe a constraint to be the number of subsets cannot be greater than sum(data_set)/target_value i.e. data_set = [5,5,5,5,5] target_value = 5 yields [5],[5],[5],[5],[5].

For context I have a large set of items I need to buy from a store, the store gives a coupon every time your purchase is over $150, if you buy everything at once you receive one coupon but if you split your items into small purchases as close to $150 as possible you will receive the maximum coupons possible.

This is the current code but it is obviously not optimized I'm having trouble scanning ahead for better matches

  1. from numpy import random
  4. def get_groups(item_list=[], target=0):
  5.     groups = []
  7.     def recurse(current_group, remaining_item_list):
  8.         for index in range(len(remaining_item_list)):
  9.             if sum(current_group) + remaining_item_list[index] &lt; target:
  10.                 current_group.append(remaining_item_list[index])
  11.                 if index+1 == len(remaining_item_list):
  12.                 groups.append(current_group)
  13.             else:
  14.                 current_group.append(remaining_item_list[index])
  15.                 groups.append(current_group)
  16.                 recurse([], remaining_item_list[index+1:])
  17.                 break
  19.     item_list.sort(reverse=True)
  20.     recurse([], item_list)
  22.     return groups
  24. items = [ random.randint(50) for i in range(21)]
  25. target = 150
  27. groups = get_groups(items, target)
  29. print(&quot;Items: {}&quot;.format(items))
  31. for index, group in enumerate(groups, start=1):
  32. print(&quot;Group {}: {}, total: {}, length: {}&quot;.format(index, group, sum(group), len(group)))

EDIT: here is some much more optimized code I am sure it is not 100% correct but its better

  1. from numpy import random
  4. def get_groups(item_list=[], target=0):
  5.     groups = []
  7.     def recurse(current_group, remaining_item_list):
  8.         for index in range(len(remaining_item_list)):
  9.             remaining_item_list.sort(reverse=True)
  10.             if sum(current_group) + remaining_item_list[index] &lt; target:
  11.                 current_group.append(remaining_item_list[index])
  12.                 if index+1 == len(remaining_item_list):
  13.                     groups.append(current_group)
  14.             elif sum(current_group) + remaining_item_list[index] &gt; target and current_group:
  15.                 reverse_search(current_group, remaining_item_list)
  16.                 remaining_item_list.sort(reverse=True)
  17.                 recurse([], remaining_item_list[index:])
  18.                 break
  19.             else:
  20.                 current_group.append(remaining_item_list[index])
  21.                 groups.append(current_group)
  22.                 recurse([], remaining_item_list[index+1:])
  23.                 break
  24.     
  25.     def reverse_search(current_group, remaining_item_list):
  26.         for index in range(len(remaining_item_list)):
  27.             remaining_item_list.sort()
  28.             if sum(current_group) + remaining_item_list[index] &lt; target:
  29.                 current_group.append(remaining_item_list.pop(index))
  30.                 if index+1 == len(remaining_item_list):
  31.                     groups.append(current_group)
  32.             else:
  33.                 current_group.append(remaining_item_list.pop(index))
  34.                 groups.append(current_group)
  35.                 current_group = []
  36.                 break
  39.     recurse([], item_list)
  41.     return groups
  43. items = [ random.randint(50) for i in range(20)]
  44. target = 150
  46. items.sort(reverse=True)
  48. print(&quot;Items: {}&quot;.format(items))
  50. groups = get_groups(items, target)
  52. for index, group in enumerate(groups, start=1):
  53.     print(&quot;Group {}: {}, total: {}, length: {}&quot;.format(index, group, sum(group), len(group)))```
  55. </details>
  58. # 答案1
  59. **得分**: 1
  61. 以下是翻译好的代码部分：
  63. ```python
  64. 以下是翻译好的代码部分：
  66. from bisect import bisect_right
  67. from itertools import combinations
  69. def bonusGroups(numbers, target):
  70.     numbers = sorted(numbers)
  71.     nbGroups = sum(numbers) // target
  72.     if not nbGroups:
  73.         return [numbers]
  74.     groups = [[] for _ in range(nbGroups)]
  76.     # build initial groups
  77.     for ig, g in enumerate(groups[:-1]):
  78.         gap = target - sum(g)
  79.         while numbers and gap > 0:
  80.             i = max(0, bisect_right(numbers, gap) - 1)
  81.             g.append(numbers.pop(i))
  82.             gap -= g[-1]
  83.         while g and min(g) <= target - sum(g):
  84.             i = g.index(min(g))
  85.             groups[ig + 1].append(g.pop(i))
  86.     groups[-1].extend(numbers)
  88.     # last group reaches target, no spreading required
  89.     if sum(groups[-1]) >= target:
  90.         return groups
  92.     return spreadGroups([*filter(None, groups)], target)
  94. # The optimization function will try to remove items from the first groups and replace them with items of subsequent groups (starting from last). The items are selected and matched up in a way that increase the subsequent group's sum without making the first group go below the target.  To keep this efficient, the logic starts by removing as few items as possible and increases the removal combination size progressively until the new spread makes all groups reach the target (or removal size exceeds the largest group's size):
  96. def spreadGroups(groups, target):
  97.     groups.sort(key=sum, reverse=True)
  98.     spreading = True
  99.     remSize = 1
  100.     while spreading and any(sum(g) < target for g in groups):
  101.         spreading = False
  102.         for ig, g in enumerate(groups[:-1]):
  103.             if remSize >= len(g):
  104.                 continue
  105.             extra = sum(g) - target
  106.             if not extra:
  107.                 continue
  108.             remSums = {sum(g[i] for i in idx): idx
  109.                        for idx in combinations(range(len(g)), remSize)}
  110.             for subSum, indexes in remSums.items():
  111.                 for tg in groups[-1:ig:-1]:
  112.                     idx = matchSum(tg, max(0, subSum - extra), subSum - 1)
  113.                     if not idx and subSum > extra:
  114.                         continue
  115.                     g.extend(tg.pop(i) for i in sorted(idx, reverse=True))
  116.                     tg.extend(g.pop(i) for i in sorted(indexes, reverse=True))
  117.                     if remSize > 1:
  118.                         ig, remSize = -1, 1
  119.                     groups[ig + 1:] = sorted(groups[ig + 1:], key=sum, reverse=True)
  120.                     spreading = True
  121.                     break
  122.                 if spreading:
  123.                     break
  124.             if spreading:
  125.                 break
  126.         if not spreading and remSize < max(map(len, groups)) - 1:
  127.             remSize += 1
  128.             spreading = True
  129.             groups.sort(key=sum, reverse=True)
  130.     return groups
  132. # In order to optimally match the total value of removed items, the target "swapping" group needs a combination of item (indexes) that adds up to the smallest total that is within the specified range.  By getting the combination with the smallest eligible total, the reduction of the source group's total is maximized and excess item values are progressively pushed down to the last groups.  This function produces a list of indexes that meet that criteria:
  134. # find group indexes producing smallest sum in range
  135. def matchSum(g, minSum, maxSum):
  136.     gsums = {0: []}
  137.     for i, n in enumerate(g):
  138.         newSums = {s + n: [*ss, i] for s, ss in gsums.items() if s + n <= maxSum}
  139.         gsums.update(newSums)
  140.     sumVal = min(gsums, key=lambda s: s if s >= minSum else maxSum + 1)
  141.     return gsums.get(sumVal, [])
  143. # Testing:
  145. items = [random.randint(50) for i in range(21)]
  146. target = 150
  148. groups = bonusGroups(items, target)
  150. print("Items: {}".format(items))
  152. for index, group in enumerate(groups, start=1):
  153.     print("Group {}: {}, total: {}, length: {}".format(index, group, sum(group), len(group)))

希望这能帮助到你！如果需要进一步的翻译或解释，请告诉我。

英文:

The following approach does not guarantee an optimal solution but it will produce one in almost all cases.

The main function starts by determining the maximum number of groups that can be formed and builds the groups by adding the largest item value that fits within the target boundary. This will produce groups that only exceed the target value by a portion of their smallest item. If the last group formed reaches the target value, then, all preceding groups also reach it and there is no additional optimization needed. If the last group does not reach the target, then an optimization function is called to swap items between groups to spread some of the extras down to the last group(s).

  1. from bisect import bisect_right
  2. from itertools import combinations
  4. def bonusGroups(numbers,target):
  5.     numbers  = sorted(numbers)
  6.     nbGroups = sum(numbers)//target
  7.     if not nbGroups: return [numbers]
  8.     groups   = [[] for _ in range(nbGroups)]
  9.     
  10.     # build initial groups
  11.     for ig,g in enumerate(groups[:-1]):
  12.         gap = target - sum(g)
  13.         while numbers and gap &gt; 0:
  14.             i = max(0,bisect_right(numbers,gap) - 1)
  15.             g.append(numbers.pop(i))
  16.             gap -= g[-1]
  17.         while g and min(g) &lt;= target-sum(g):
  18.             i = g.index(min(g))
  19.             groups[ig+1].append(g.pop(i))
  20.     groups[-1].extend(numbers)
  22.     # last group reaches target, no spreading required
  23.     if sum(groups[-1]) &gt;= target:
  24.         return groups
  26.     return spreadGroups([*filter(None,groups)],target)

The optimization function will try to remove items from the first groups and replace them with items of subsequent groups (starting from last). The items are selected and matched up in a way that increase the subsequent group's sum without making the first group go below the target. To keep this efficient, the logic starts by removing as few items as possible and increases the removal combination size progressively until the new spread makes all groups reach the target (or removal size exceeds the largest group's size):

  1. def spreadGroups(groups,target):
  2.     groups.sort(key=sum,reverse=True)
  3.     spreading = True
  4.     remSize   = 1
  5.     while spreading and any(sum(g) &lt; target for g in groups):
  6.         spreading = False
  7.         for ig,g in enumerate(groups[:-1]):
  8.             if remSize &gt;= len(g): continue
  9.             extra   = sum(g)-target
  10.             if not extra: continue
  11.             remSums = { sum(g[i] for i in idx):idx
  12.                         for idx in combinations(range(len(g)),remSize) }
  13.             for subSum,indexes in remSums.items():
  14.                 for tg in groups[-1:ig:-1]:
  15.                     idx = matchSum(tg,max(0,subSum-extra),subSum-1)
  16.                     if not idx and subSum&gt;extra: continue
  17.                     g.extend(tg.pop(i) for i in sorted(idx,reverse=True))
  18.                     tg.extend(g.pop(i) for i in sorted(indexes,reverse=True))
  19.                     if remSize&gt;1: ig,remSize = -1,1
  20.                     groups[ig+1:] = sorted(groups[ig+1:],key=sum,reverse=True)
  21.                     spreading = True
  22.                     break
  23.                 if spreading: break
  24.             if spreading: break
  25.         if not spreading and remSize &lt; max(map(len,groups))-1:
  26.             remSize  += 1
  27.             spreading = True
  28.             groups.sort(key=sum,reverse=True)           
  29.     return groups

In order to optimally match the total value of removed items, the target "swapping" group needs a combination of item (indexes) that adds up to the smallest total that is within the specified range. By getting the combination with the smallest eligible total, the reduction of the source group's total is maximized and excess item values are progressively pushed down to the last groups. This function produces a list of indexes that meet that criteria:

  1. # find group indexes producing smallest sum in range
  2. def matchSum(g,minSum,maxSum):
  3.     gsums = {0:[]}
  4.     for i,n in enumerate(g):
  5.         newSums = { s+n:[*ss,i] for s,ss in gsums.items() if s+n&lt;=maxSum }
  6.         gsums.update(newSums)
  7.     sumVal  = min(gsums,key=lambda s:s if s&gt;=minSum else maxSum+1)
  8.     return gsums.get(sumVal,[])

Testing:

  1. items = [ random.randint(50) for i in range(21)]
  2. target = 150
  4. groups = bonusGroups(items, target)
  6. print(&quot;Items: {}&quot;.format(items))
  8. for index, group in enumerate(groups, start=1):
  9.     print(&quot;Group {}: {}, total: {}, length: {}&quot;.format(index, group, sum(group), len(group)))

Test outputs:

  1. Items: [38, 38, 31, 9, 42, 25, 22, 42, 44, 46, 43, 47, 14, 20, 38, 34, 35, 3, 49, 36, 30]
  2. Group 1: [49, 47, 46, 3, 9], total: 154, length: 5
  3. Group 2: [44, 43, 42, 20, 14], total: 163, length: 5
  4. Group 3: [42, 38, 38, 31, 22], total: 171, length: 5
  5. Group 4: [25, 30, 34, 35, 36, 38], total: 198, length: 6
  7. Items: [34, 5, 13, 30, 27, 15, 4, 44, 33, 13, 25, 41, 33, 23, 14, 8, 39, 9, 33, 8, 4]
  8. Group 1: [44, 41, 39, 25, 4], total: 153, length: 5
  9. Group 2: [34, 33, 33, 33, 15, 4], total: 152, length: 6
  10. Group 3: [5, 8, 8, 9, 13, 13, 14, 23, 27, 30], total: 150, length: 10
  12. Items: [25, 22, 44, 42, 43, 22, 25, 16, 42, 24, 21, 5, 4, 16, 3, 22, 46, 31, 11, 24, 14]
  13. Group 1: [46, 44, 43, 16, 3], total: 152, length: 5
  14. Group 2: [42, 42, 31, 25, 5, 4, 11], total: 160, length: 7
  15. Group 3: [14, 16, 21, 22, 22, 22, 24, 24, 25], total: 190, length: 9

答案2

得分: 0

以下是优化后的方法，它按降序对数组进行排序，然后尝试构建尽可能大的子集，然后再移动到下一个子集。如果下一个项目太大，它会继续下一个。它还包括动态规划，减少了所进行的检查数量。

  1. from typing import List
  3. def get_groups(item_list: List[int], target: int) -> List[List[int]]:
  4.     groups = []
  5.     remainder = []
  7.     # 降序排序列表
  8.     item_list.sort(reverse=True)
  10.     while item_list:
  11.         group = []
  12.         for item in item_list[:]:
  13.             if sum(group) + item <= target:
  14.                 group.append(item)
  15.                 item_list.remove(item)
  16.         if group:
  17.             groups.append(group)
  18.         else:
  19.             remainder = item_list
  20.             break
  22.     groups.append(remainder)
  24.     return groups
  26. # 随机生成器已被静态列表替代，以保证可重现性
  27. items = [1,2,3,4,5,6,7,8,9,10]
  28. target = 5
  30. groups = get_groups(items, target)
  32. print("Items: {}".format(items))
  34. for index, group in enumerate(groups, start=1):
  35.     print("Group {}: {}, total: {}, length: {}".format(index, group, sum(group), len(group)))

注意：上述代码已经翻译成中文，只包括代码部分。

英文:

Here's an optimized approach which sorts the array in descending order, then tries to build the maximum subset possible before moving to the next subset. If the next item is too large, it moves on to the next one. It also incorporates dynamic programming, reducing the number of checks made.

  2. from typing import List
  4. def get_groups(item_list: List[int], target: int) -&gt; List[List[int]]:
  5.     groups = []
  6.     remainder = []
  8.     # sort list in descending order
  9.     item_list.sort(reverse=True)
  11.     while item_list:
  12.         group = []
  13.         for item in item_list[:]:
  14.             if sum(group) + item &lt;= target:
  15.                 group.append(item)
  16.                 item_list.remove(item)
  17.         if group:
  18.             groups.append(group)
  19.         else:
  20.             remainder = item_list
  21.             break
  23.     groups.append(remainder)
  25.     return groups
  27. # random generator is replaced with a static list for reproducibility
  28. items = [1,2,3,4,5,6,7,8,9,10]
  29. target = 5
  31. groups = get_groups(items, target)
  33. print(&quot;Items: {}&quot;.format(items))
  35. for index, group in enumerate(groups, start=1):
  36.     print(&quot;Group {}: {}, total: {}, length: {}&quot;.format(index, group, sum(group), len(group)))

huangapple
  • 本文由 发表于 2023年6月29日 03:12:45
  • 转载请务必保留本文链接：https://go.coder-hub.com/76576089.html
  • best-fit
  • combinations
  • python
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定