How can I use domain knowledge to improve this algorithm? Ugh, the weights

Question

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

This problem equates to the following situation:

• On a table are a scattering of weights of various mass.
• In your hand are a few weights of various mass.
• If there is a combination of weights on the table that have a mass matching one in your hand, you can take those weights from the table, because they weigh the same as the single weight in your hand. You can drop the whole thing, including the weight from your hand, into your bucket.
• You can pick up more than one combination of weights as long as they all match the one in your hand, and drop all of them into your bucket.
• You score points depending on how heavy your bucket is.
• You can drop a weight onto the table if it helps you take more weights later.

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)

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?

Thanks!

Answer 1

This problem is a variation of the bin-packing problem.

Bin packing problem in a nutshell:

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:

• Your "bins" have changing weights (and by setting T1=T2=...=T we can mimic the bin packing problem).
• Checking if you can fill up all bins exactly is an optimal solution to both problems.

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

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, finding optimal solution to integer linear programming equations is also done in exponential time in worst case.