arrays - 用不同维度的项目填充包的算法逻辑

Question

我正在为我正在开发的应用程序编写一些传送功能。其中一项要求是找到确定哪些元素可以放入盒子中的最有效方法。我们还有一个要求，即一次只能将两件元素放入任何一个盒子中，并且它们必须完全适合盒子，没有剩余空间。

我们将通过假设盒子和元素的大小是整数(而不是实际尺寸)来简化问题。

我需要编写一个函数，将项目大小数组和盒子大小作为参数，并检查是否有任何两个项目可以完美地放入盒子中。

例如，假设我们想要查看 2 个项目是否正好填满尺寸为 4 的框。 尺寸为 1 和 2 的 2 件商品将无法使用，因为箱子中有 1 个单位的可用空间。

因此输入 {Item Sizes: [1,2], target: 4} 将返回 false

示例输入和输出:

input: {Item Sizes: [1,3,5], target: 2} output: false
input: {Item Sizes: [1,1,3,5], target: 2} output: true
input: {Item Sizes: [1,3,5], target: 4} output: true
input: {Item Sizes: [1,3,5,4], target: 7} output: true

显然，我可以通过循环运行数组并将每两个数字相加以检查它们是否等于框大小，但我需要一种更有效的方法。如果我们这样做，数组中每增加一项，计算量就会呈指数增长。例如，给定这些参数...

input: {Item Sizes: [1,3,5,4], target: 7} output: true

如果我没记错的话(1+3、1+5、1+4、3+1、3+5、3+4 等)，以这种方式完成需要 12 次计算。但是，如果我们再向数组中添加一项，就像这样......

input: {Item Sizes: [1,3,5,4,6], target: 7} output: true

需要 20 次计算。如果 "n"等于数组中的项目数，则公式将如下所示...

n * (n-1)

从“n”中减去一个，因为您无法对照该项目本身进行检查。 检查 1000 项的数组需要 999000 次计算。

优化的一种方法是删除数组中任何大于框大小的整数，并在找到匹配项后立即跳出函数。

必须有更好的方法来优化它。任何帮助将不胜感激。

谢谢。

Answer 1

首先，请注意一般问题(每箱无限数量的元素)是 NP-Hard，实际上是子集和问题。

为了限制每个盒子只有两个项目，可以在单次数据传递中完成，使用哈希表(如果盒子的大小不太大，则使用数组)，并存储与盒子的大小。

python 代码:

def FindPair(array, box_size):
  s = {} #empty dictionary
  for (i,x)  in enumerate(array):
    if x > box_size:
      continue
    if x in s:
      print 'match for indices:', i, s[x]
      return True
    else:
      s[box_size - x] = i
  return False

print FindPair([1,3,5], 2)
print FindPair([1,1,3,5], 2)
print FindPair([1,3,5], 4)
print FindPair([1,3,5,4], 7)