declare @flat table
    id int not null,
    percentage int not null,
    value float not null

insert into @flat (id, percentage, value)
select 1,10,0.333
union all
select 1,20,0.4
union all
select 2, 50, 0.5
union all
select 2, 70, 0.67
union all
select 3, 10, 0.125
union all
select 3, 40, 0.325

having this sample data, how could i determine the rows that maximize the sum of the values ? Having the following conditions:

  • one percentage per id only
  • the sum of the percentages must be 100

there is two possible solutions:

-- id percentage  value     sum
--  1     10      0.333    0.333  
--  2     50      0.5      0.833 
--  3     40      0.325    1.158

-- id percentage  value     sum
--  1     20      0.4       0.4  
--  2     70      0.67      1.070 
--  3     10      0.125     1.195

but it matters only the last one.

  • 1
  • What did you try? – Colin 't Hart Feb 26 '14 at 16:16
  • i thought i could use something similar like "the coin change" algorithm, where i was retrieving percentages until 0 reached using a recursive cte..no success. using code select id, (select top 1 percentage from @flat as t2 where t2.id=t1.id order by percentage desc) as percentage from @flat as t1 group by id i don't know how to force a running total percentage of 100 – rezanov Feb 26 '14 at 16:34

Congratulations, you have a subset sum problem! It's an NP-complete problem. Arriving at the solution is going to call for brute force. i.e. Generate and test all possible subsets. WARNING: This may involve the sketchy Cartesian products your mother warned you about.

Depending on the size of your actual data domain, in SQL that is going to range from "computationally expensive but it works" at best to "who jammed the kernel to 100% and crashed the database server?" at worst.

As a computationally-intensive problem, it is more advisable to solve it in a dynamic programming language than in a SQL DBMS.

| improve this answer | |
  • Yes but the specific question has a small "P" value so I guess solving it won't be too intensive. – ypercubeᵀᴹ Feb 26 '14 at 20:15
  • That presumes that the P value needed for the real-world problem is accurately represented by poster's example. It may be simplified, as such examples often are. But yes, for OP's sake, hopefully it's a manageable amount of brute force. – Jonathan Van Matre Feb 26 '14 at 20:23
  • i was able to find the solution using brute force, but its not a generic solution, since i need to add or subtract a "cross apply" to get all the products. – rezanov Feb 26 '14 at 21:20

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.