Q:

How likely will Tom's bag be heavier than Sally's bag?

Tom and Sally each have 50 cantaloupes that each weigh integer values from 0 to 1500 ounces inclusive. They each randomly bag 20 of their own cantaloupes. What's the probability that Tom's bag weighs at least 1.5 that of Sally's given the weights of all 100 canteloupes?
I modeled this question as a function that takes as input two int arrays each of size 50 and returns a double from 0 to 1. I tried to list all combinations of size 20 for the values in the arrays and then, for each combination of Tom's weights, loop through all of Sally's combinations and count how many are less than 1.5 times Tom's bag weight. However, this method has proven way too slow.
Is there a faster way? Or am I resigned to this I believe exponential method. 

A:

Since C(50,20) = 47,129,212,243,960, but 1500x20 = 30,000,
it would be more useful to build two arrays (for Tom and for Sally), each of size 30,000, and count in each index i the number of combinations (out of the total C(50,20) combinations) with total weight i.
Comparing the probabilities of S(Sally)<1.5*S(Tom) using such arrays is a manageable task.
The main question is can we build such arrays faster than calculating the 47,129,212,243,960 sums? In other words - can we find out effectively how many subsets of size 20 sum up to any of the 30,000 possible values?
A dynamic programming approach to the subset-sum problem is very practical in this case, as it requires only 50 * 20 * 1500 arithmetic operations.

