我有平衡的麻烦。我觉得我失去了一些东西。

I am having balancing trouble. I feel like I'm missing something here..

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

This problem equates to the following situation:

在一个表中各种质量权重的分散。 在你的手有各种质量的几个权重。 如果存在有一团在手上匹配的那个桌子上权重的组合，你可以把这些权重从表中，因为他们的体重一样的单件重量在手中。可以删除整个事情，包括从你手上的重量，为你的水桶。 您可以捡起一个以上的组合，只要它们都符合一个在你的手，并丢弃所有的人都变成你的水桶。 您取决于多么沉重的水桶得分。 您可以删除重到表，如果它可以帮助你以后采取更多的权重。

目前为止最大限度地点数涨幅我最好的尝试是：

My best attempt at maximizing point gain so far is:

找到在桌子上的权重的数目的所有整数分区。 置换表上的所有的权重，使他们形成每一个可能的独特的群体配合上述的分区。 看看在手比赛的权重。 在另外一次，包括每个在手的权重，看看是否下降，体重会产生更多的从长远来看，不是简单地挑选一些了起来。 （也就是说，如果的这个的权重分别对表） Find all integer partitions of the number of weights on the table. Permute all weights on the table so that they form every possible unique group fitting the above partitions. See if a weight in the hand matches. In addition, one at a time, include each of the weights in hand and see if dropping that weight would yield more in the long run than simply picking some up. (i.e. what if this weight were on the table)

我的问题是：这工作，但它是缓慢的。我得到的Andr​​oid 4.4.4跳帧仅7中选择的权重，在银河注4。

My problem is: This works, but it is slow. I get skipped frames on Android 4.4.4 with only 7 weights selected, on a Galaxy Note 4.

我觉得我失去了一些重要的节省时间的问题域，但对我的生活，我觉得视而不见。那么，你将如何解决这个特殊的难题？

I feel like I'm missing some crucial time-saver in the problem domain, but for the life of me I feel blind to it. So, how would you solve this particular puzzle?

谢谢！

推荐答案

这个问题是仓的变化 - 包装问题的。

斌简而言之包装问题：

给定一组项目，每个重量无线，一个纸槽容量 T ，和（天然）   数 K - 找出如果你可以使用最多 K 箱，其中每个   包含与加权和 T ，使得所有的元素都是元素   覆盖。

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.

您的问题是它的一个非常密切的变化，而且有些它的一个概括：

Your problem is a very close variation of it, and somewhat a generalization of it:

您的垃圾桶已经改变权重（通过设置T1 = T2 = ... = T，我们可以模仿装箱问题）。 检查，如果你能填满所有的垃圾箱恰恰是这两个问题的最佳解决方案。

您的问题是definetly NP完全和减少从binpacking或简单甚至从子集求和问题。

Your problem is definetly NP-Complete, and a reduction is simple from binpacking or even from subset-sum-problem.

此外，由于binpacking问题是强NP完全问题，这两个问题的相似性太大，无法忽视，我相信这个问题也是强烈-NP完全问题，这意味着没有已知的伪多项式解决的办法为好。

Moreover, since the binpacking problem is Strongly NP-Complete problem, and the similarity of the two problems is too large to ignore, I believe this problem is also Strongly-Np-Complete, which means there is no known pseudo-polynomial solution to it as well.

这是一个坏消息，它意味着蛮力解决方案，类似于你做了什么，是要走的路。 还可以尝试使用线性规划解决这个问题，并按照优化方程：

This is a bad news, and it means a brute force solution, similar to what you have done, is the way to go. You can also try to solve it with linear programming, and follow the optimization equations:

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

Unfortuntaely，寻找最佳的解决方案，以整数线性规划方程组也在最坏的情况下进行的指数时间。

Unfortuntaely, finding optimal solution to integer linear programming equations is also done in exponential time in worst case.