Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.
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.

share|improve this question
1  
    
What did you try? –  Colin 't Hart Feb 26 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 at 16:34

1 Answer 1

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.

share|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 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 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 at 21:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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