So I just had discussion with a friend about a theoretical situation were he was to populate a server mother board with ram modules in his garage..
So lets assume there are 48 ram slots available to populate each with one of the 7 different capacities of ram available* (1GB,2,4,8,16,32,64) in order to achieve a total of 1TB (or else 1024 GB) of total capacity.
How many possible combinations are there to achieve this? which is the most efficient way to find out?
*you could use each available capacity more than once obviously but I would also like your thoughts on the scenario were you could use them all the combinations of numbers of capacities you like + use just SOME of the group at your discretion e.g just 64 and 32GB sticks and none of the other capacities etc.
Best Answer
This is a dynamic programming problem where there is a base case (Base Case: With $0$ slots, there is $1$ way to create $0$ GB of RAM) and induction (Induction: Using the number of ways to create any sum up to the maximum with $n-1$ slots, we can find the number of ways to get a sum to $s$ with $n$ slots by summing the number of ways to get a sum to $s-a$ with $n-1$ slots for all addends $a$). This is also similar to the subset sum, but instead of figuring out whether or not we can get a sum with $1024$ GB, we're finding the number of ways we can do so. This means that this problem is NP-complete, which basically means the time to solve the problem grows very fast as the addends and/or the sum are added with more digits.
Thus, here is my dynamic programming algorithm for this problem in Python:
Also, please note that my program accounts for the order in which the slots are filled , so the situation where $1$ GB is put in the first RAM slot and $2$ GB is put in the second RAM slot and the situation where $2$ GB is put in the first RAM slot and $1$ GB is put in the second RAM slot are treated as the different situation and are counted as $2$ ways to sum to $3$ with $2$ addends. Also, I leave no RAM slot empty, so each RAM slot has at least $1$ GB of RAM.
My program outputs $54725807780812926153007692867349522953$ as an answer, meaning that there are $54725807780812926153007692867349522953$ ways to sum to $1024$ GB using $48$ RAM slots with either $1$, $2$, $4$, $8$, $16$, $32$, and $64$ GB of RAM while account for the order in which the RAM slots are filled and leaving no RAM slot empty.