Finding combinations of rows that combined do not exceed a value in mySQL -

this question requires explanation.

• assume have table items.
• each item has multiple characterics, called id, score, value , size (all integers).
• some of items grouped unknown groups of 3
• each item can in 0 or 1 group
• each group (another table) lists amount of items (3) , combined score, size , value of 3 items

example table items

tables:

items(id,size,score,value) group(grpid,tsize,tscore,tvalue) 

example content

items(1,2000,3000,4000)     ,(2,4000,5000,8000)     ,(3,8000,3000,1000)     ,(4,12000,1000,400)  groups(1,14000,11000,13000) -> matches item 1,2,3 combined 

imagine items table has hundreds 1000 records , typically 10 groups of 3 items

followup question: 4, 5 or 10 sized groups.

what efficient way find possible groups (in theory search find more 1 combination of 3 items match groups totals)?

welcome unlucky ones: encountered subset sum problem, np-complete , not solvable in polynomial time in general. (more or less) restricted problem groups of size k=3, eases little bit. nevertheless have k * number_of_items possibilities, quite lot. since did not specify further information, assume 1 must try possible combinations.

actually not see easy solution how can solve problem. sure can try , join table 3 times.

this returns possible groups:

select a.id a_id, b.id b_id, c.id c_id,   (a.score + b.score + c.score) score_sum,   (a.value + b.value + c.value) value_sum,   (a.size + b.size + c.size) size_sum items inner join items b on b.id < a.id inner join items c on c.id < b.id 

one can sort out triples represent equivalent solutions, permute between a, b , c. can achieved constraining ids lower current one.

then must compare available groups:

select a_id, b_id, c_id, groups.id   (select a.id a_id, b.id b_id, c.id c_id,     (a.score + b.score + c.score) score_sum,     (a.value + b.value + c.value) value_sum,     (a.size + b.size + c.size) size_sum   items   inner join items b on b.id < a.id   inner join items c on c.id < b.id ) inner join groups on a.score_sum = groups.score   , a.value_sum = groups.value   , a.size_sum = groups.size 

though not expect run fast. speeding possible exploiting particular problem.

you might re-think if there additional information can solve particular problem, or try modify base data.