android - 我如何使用领域知识来改进这个算法？呃，重量

Question

我在平衡方面遇到了麻烦。我觉得我在这里遗漏了一些东西..

这个问题等同于以下情况:

• table 上散布着各种质量的砝码。
• 你手里拿着几个不同质量的砝码。
• 如果 table 上有一组重量与您手中的重量相匹配的重量，您可以从 table 上拿走这些重量，因为它们的重量与您手中的单个重量相同。你可以把整个东西，包括你手上的重量，都放到你的桶里。
• 您可以拿起不止一种重量组合，只要它们都与您手中的重量相匹配，然后将它们全部放入您的桶中。
• 您的分数取决于您的水桶的重量。
• 你可以在 table 上放一个重物，如果它有助于你以后再举重物的话。

到目前为止，我在最大化点增益方面的最佳尝试是:

• 找出表中权重个数的所有整数分区。
• 排列表中的所有权重，使它们形成适合上述分区的每个可能的唯一组。
• 看看手上的重量是否匹配。
• 此外，一次一个，包括手上的每个重量，看看从长远来看，放下重量是否会比简单地拿起一些重量产生更多。 (即如果这个重量在 table 上怎么办)

我的问题是:这有效，但速度很慢。在 Galaxy Note 4 上，我在 Android 4.4.4 上跳帧，只选择了 7 个权重。

我觉得我在问题领域中错过了一些重要的节省时间的方法，但对于我的一生来说，我对此视而不见。那么，您将如何解决这个特殊难题？

谢谢!

Answer 1

此问题是 bin-packing problem 的变体.

简而言之装箱问题:

Given a set of items, each with weight wi, a bin capacity T, and a (natural) number k - find out if you can use at most k bins, where each contains elements with weight sum T, such that all elements are covered.

你的问题是它的一个非常接近的变体，并且在某种程度上是它的概括:

• 您的“箱子”具有不断变化的重量(通过设置 T1=T2=...=T 我们可以模拟装箱问题)。
• 检查您是否可以准确地填满所有垃圾箱是解决这两个问题的最佳解决方案。

你的问题绝对是NP-Complete ，并且从 binpacking 甚至从子集求和问题中进行归约很简单。

此外，由于binpacking问题是Strongly-NP-Complete问题，而且两个问题的相似度大到无法忽略，我相信这个问题也是Strongly-Np-Complete，也就是说没有已知的伪多项式也可以解决。

---

这是一个坏消息，这意味着与您所做的类似的蛮力解决方案是可行的方法。
你也可以尝试用linear programming来解决。 ，并遵循优化方程:

maximize: 
   sum {y_i * T_i}
s.t.:
  sum { x_i,j * w_j | sum over all j's} = y_i * T_i         for all i
  sum { x_i,j | sum over all i's } <= 1                     for all j
  x_i,j =0,1
  y_i =0,1

不幸的是，在最坏的情况下，寻找整数线性规划方程的最优解也是在指数时间内完成的。