1

I have 36 data of box with weights:

24.8
24.7
24.6
24.6
24.65
24.75
25.1
24.7
24.7
24.9
24.8
24.65
24.85
24.85
24.7
24.75
25
24.6
24.55
24.6
24.5
24.55
24.5
24.85
24.7
24.65
24.4
24.4
24.55
24.45
24.35
24.95
24.65
24.85
24.75
25

Which combination of 12 boxes to get results of 296.35? Can I can provide this with stored procedure or cross join in MySQL?

The query to insert are:

insert tbl(weight) values(24.8);
insert tbl(weight) values(24.7);
insert tbl(weight) values(24.6);
insert tbl(weight) values(24.6);
insert tbl(weight) values(24.65);
insert tbl(weight) values(24.75);
insert tbl(weight) values(25.1);
insert tbl(weight) values(24.7);
insert tbl(weight) values(24.7);
insert tbl(weight) values(24.9);
insert tbl(weight) values(24.8);
insert tbl(weight) values(24.65);
insert tbl(weight) values(24.85);
insert tbl(weight) values(24.85);
insert tbl(weight) values(24.7);
insert tbl(weight) values(24.75);
insert tbl(weight) values(25);
insert tbl(weight) values(24.6);
insert tbl(weight) values(24.55);
insert tbl(weight) values(24.6);
insert tbl(weight) values(24.5);
insert tbl(weight) values(24.55);
insert tbl(weight) values(24.5);
insert tbl(weight) values(24.85);
insert tbl(weight) values(24.7);
insert tbl(weight) values(24.65);
insert tbl(weight) values(24.4);
insert tbl(weight) values(24.4);
insert tbl(weight) values(24.55);
insert tbl(weight) values(24.45);
insert tbl(weight) values(24.35);
insert tbl(weight) values(24.95);
insert tbl(weight) values(24.65);
insert tbl(weight) values(24.85);
insert tbl(weight) values(24.75);
insert tbl(weight) values(25);

1 Answer 1

0
SELECT  t1.weight,
        t2.weight,
        t3.weight,
        ...
        t12.weight
    FROM tbl t1
    JOIN tbl t2  ON t2.weight > t1.weight
    JOIN tbl t3  ON t3.weight > t2.weight
    ...
    JOIN tbl t12  ON t12.weight > t11.weight
    WHERE t1.weight +
          t2.weight +
          t3.weight +
          ...
          t12.weight  = 296.35;

Possible issues:

  • What I provided does not allow for duplicate weights. If that can happen, I need an id or something instead of weight for avoiding dups.
  • If you want the closest, not exact, match:

Replace the WHERE clause with something like:

    ORDER BY ABS( t1.weight + ... + t12.weight - 296.35 ) ASC
    LIMIT 1

This would probably run a lot faster in any programming language then SQL.

I worry that this query will not complete in my lifetime. I think it would take billions, maybe trillions of iterations.

OR

The code above is "brute force". With some more thinking, it should be possible to 'prune' the list to cut back significantly (down from trillions to billions??) the amount of work. But that would need a recursive CTE (upgrade to MySQL 8.0) or, as I say, use a real programming language.

4
  • Thx u for the input it really help me way of thinking. Btw is there really another way not using stored procedure but using another progamming language like delphi or visual basic or php to do this but in timely manner (i mean it can finish the calculation in 1 day not trilion years)
    – Ekkai Imwe
    Dec 6, 2016 at 6:40
  • Oops, my code is not correct because of dup values existing in the table.
    – Rick James
    Dec 6, 2016 at 6:46
  • Find a book or research paper on combinatorics. See if they have the algorithm. Then come back; we may be able to turn it into SQL. The code I gave you (plus some fix for dups) is the best I know of off hand. It might take 36! / ( 24! * 12! ) operations. That's still a big number.
    – Rick James
    Dec 6, 2016 at 6:49
  • An advantage of a non-SQL approach is that you can terminate the algorithm when you come "close enough". My gut says that will happen after millions of operations instead of billions.
    – Rick James
    Dec 6, 2016 at 6:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.