Clever Geek Handbook

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

I am having problems with balancing. I feel like I am missing something here.

This problem equates to the following situation:

  • The table shows the dispersion of weights of different masses.
  • You are holding several weights of various masses.
  • If the table has a combination of weights that match the mask in your hand, you can take those weights from the table because they weigh the same as one weight in your hand. You can throw all of this, including the weight from your hand, into your bucket.
  • You can choose more than one combination of weights, as long as they all match the one in your hand, and drop all of them in your bucket.
  • You score points based on how heavy your bucket is.
  • You can shed weight on the table if it helps you take more weight later.

My best attempt at maximizing point gain so far:

  • Find all integer partitions of the number of weights in the table.
  • Transfer all weights to the table so that they form every possible unique group corresponding to the above sections.
  • See if the weight in your hand is correct.
  • Also, one at a time, turn on each of the weights available and see if losing weight can weigh more in the long run than just putting on a little. (that is, if this weight was on the table)

My problem: it works, but it is slow. I am dropping frames on Android 4.4.4 with 7 weights selected on galaxy 4.

I feel like I am missing some important time saving in the problem area, but for my life I feel blindly. So how would you solve this riddle?

Thank!

+3


source to share


1 answer


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

Bean packing problem in a nutshell:

Given a set of elements, each with a weight wi

, bin capacity T

and (natural) number k

- see if you can use no more than k

bins, where each contains weighted elements T

so that all elements are covered.

Your problem is a very close variation and somewhat generalization:

  • Your "baskets" change weight (and by setting T1 = T2 = ... = T we can simulate the problem of packing the basket).
  • Making sure you can fill all the bins is the best solution to both problems.

Your problem is definitely NP-Complete and the abbreviation is simple from binpacking or even from subset problem.



Also, since the binpacking problem is an NP-Complete problem and the similarity of the two problems is too great to ignore, I believe this problem is also Strong-Np-Complete, which means there is no known pseudopolynomial solution for it.

This is bad news, and it means a brute force solution similar to what you did 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 } <= 1                     for all j
  x_i,j =0,1
  y_i =0,1

Unfortunately, finding the optimal solution to integer linear programming equations also runs in exponential time in the worst case.

+2


source






More articles:


All Articles