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

Question

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

我们将通过假设盒子和物品的尺寸是整数（而不是实际尺寸）来简化问题。

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

例如，假设我们想要查看 2 件商品是否正好填满尺寸为 4 的方框。尺寸为 1 和 2 的 2 件商品将无法使用，因为包装盒中有 1 件免费 space。

因此输入 {Item Sizes: [1,2], target: 4} 会 return 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, etc.） .但是，如果我们再向数组中添加一项，就像这样...

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

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

n * (n-1)

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

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

一定有更好的优化方法。任何帮助将不胜感激。

谢谢。

Answer 1

首先，请注意一般问题（每箱无限数量的物品）是 NP-Hard，实际上是子集和问题。

为了限制每个盒子恰好有两个项目，可以使用散列 table（如果盒子的大小不太大，则可以使用数组）在单次数据传递中完成, 并存储盒子大小的差异。

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)

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

Algorithm logic for filling packages with items of different dimensions

arrays

algorithm

math

logic