如何获取 2 表数据，并提出符合限制的组合

Question

所以，我想做的是在这里使用这两个表，并从 Table 1 中得出项目组合，总计Table 2 + 1500 或更少的总和，但永远不能低于 Table 2[=33= 的值] + 500。然后在最后它应该 return 稍后将在其余代码中使用的组合。

例如，假设我们想出了一个组合，这个组合使用了 Table 2 中的所有 4 个项目，我们可以使用所有这些项目，因为它符合限制，现在如果我们添加所有Table 2 中的值得到 11,620。现在我们必须从 Table 1 中得出一个组合，其值至少为 12,120 但小于 13,120。

如果您需要有关我要在此处存档的内容的更多详细信息，请告诉我！

限制

每个组合最多只能有 4 个项目

每个项目的值由“值”定义。

Table 2

[ { "UAID":143071570, "assetId":19027209, "name":"Perfectly Legitimate Business Hat", "value":10549 }, { "UAID":143334875, "assetId":19027209, "name":"Perfectly Legitimate Business Hat", "value":10549 }, { "UAID":1235149469, "assetId":100425864, "name":"Deluxe Game Headset", "value":1795 }, { "UAID":2756318596, "assetId":20573078, "name":"Shaggy", "value":1565 }, { "UAID":3499638196, "assetId":20573078, "name":"Shaggy", "value":1565 }, { "UAID":11002211144, "assetId":102618797, "name":"DJ Remix's Goldphones", "value":7393 }, { "UAID":50913661583, "assetId":4390875496, "name":"Diamond Crystal Circlet", "value":4886 } ]

Table 2

[ { "UAID":672099668, "assetId":60888284, "name":"DarkAge Ninjas: Dual Kamas", "value":4461 }, { "UAID":6599510068, "assetId":554663566, "name":"Manicbot 10000", "value":4319 }, { "UAID":63414825508, "assetId":91679217, "name":"Sailing Hat", "value":1886 }, { "UAID":150428091864, "assetId":8785277745, "name":"Cincinnati Bengals Super Bowl LVI Helmet", "value":954 } ]

Answer 1

这是我多次展示过的技术，其他人似乎都没有听说过。

思路和Finding all possible combinations of numbers to reach a given sum一样，但是比较复杂，需要反复做。它是创建一个数据结构，从中可以很容易地找到总和为特定值的子集。

class SubsetSumIter:
    def __init__ (self, data):
        self.data = data

        # Build up an auxilliary data structure to find solutions.
        last_index = {0: [-1]}
        for i in range(len(data)):
            for s in list(last_index.keys()):
                new_s = s + data[i]['value']
                if new_s in last_index:
                    last_index[new_s].append(i)
                else:
                    last_index[new_s] = [i]

        self.last_index_by_target = last_index
        self.targets = sorted(last_index.keys())

    def subsets_at_target(self, target, max_i=None):
        if max_i is None:
            max_i = len(self.data)

        for i in self.last_index_by_target[target]:
            if i == -1:
                yield [] # empty sum
            elif max_i <= i:
                break # went past our solutions
            else:                                                                                                              
                for answer in self.subsets_at_target(target - self.data[i]["value"], i):
                    answer.append(self.data[i])
                    yield answer

    def subsets_in_range(self, lower, upper):
        i_min = 0
        i_max = len(self.targets)
        while 1 < i_max - i_min:
            i_mid = (i_min + i_max) // 2
            if self.targets[i_mid] < lower:
                i_min = i_mid
            else:
                i_max = i_mid

        i = i_min + 1
        while i < len(self.targets) and self.targets[i] <= upper:
            for answer in self.subsets_at_target(self.targets[i]):
                yield answer
            i = i+1

由此我们可以创建您想要的加入条件，如下所示：

def complex_join(table1, table2):
    iter1 = SubsetSumIter(table1)
    iter2 = SubsetSumIter(table2)

    # For each sum from table2
    for target in iter2.targets:
        # For each combination from table 1 in our desired range
        for subset1 in iter1.subsets_in_range(target + 500, target + 1500):
            # For each combination from table 2 that gets that target
            for subset2 in iter2.subsets_at_target(target):
                yield (subset1, subset2)

并找到您的示例的所有 38 个解决方案：

t1 = [
   {
      "UAID":143071570,
      "assetId":19027209,
      "name":"Perfectly Legitimate Business Hat",
      "value":10549
   },
   {
      "UAID":143334875,
      "assetId":19027209,
      "name":"Perfectly Legitimate Business Hat",
      "value":10549
   },
   {
      "UAID":1235149469,
      "assetId":100425864,
      "name":"Deluxe Game Headset",
      "value":1795
   },
   {
      "UAID":2756318596,
      "assetId":20573078,
      "name":"Shaggy",
      "value":1565
   },
   {
      "UAID":3499638196,
      "assetId":20573078,
      "name":"Shaggy",
      "value":1565
   },
   {
      "UAID":11002211144,
      "assetId":102618797,
      "name":"DJ Remix's Goldphones",
      "value":7393
   },
   {
      "UAID":50913661583,
      "assetId":4390875496,
      "name":"Diamond Crystal Circlet",
      "value":4886
   }
]

t2 = [
  {
     "UAID":672099668,
     "assetId":60888284,
     "name":"DarkAge Ninjas: Dual Kamas",
     "value":4461
  },
  {
     "UAID":6599510068,
     "assetId":554663566,
     "name":"Manicbot 10000",
     "value":4319
  },
  {
     "UAID":63414825508,
     "assetId":91679217,
     "name":"Sailing Hat",
     "value":1886
  },
  {
     "UAID":150428091864,
     "assetId":8785277745,
     "name":"Cincinnati Bengals Super Bowl LVI Helmet",
     "value":954
  }
]


for answer in complex_join(t1, t2):
    print(answer)

如果你想在最后得到一个（可能很大的）列表，你可以简单地 list(complex_join(t1, t2))。

如何获取 2 表数据，并提出符合限制的组合

How to take 2 Tables of data, and come up with combination that fit the restrictions

python

algorithm

math