Counting Possible Combinations of WeightsDate: 10/07/2004 at 20:09:18 From: Sean Subject: Number of possible combinations of weights Dear Dr. Math - If you have a set of weights, in sizes 50g, 25g, 15g, and 5g, how would you go about determining how many possible combinations of weights you could make to equal 85g? I am trying to help my daughter with her homework, and must confess to being a bit stumped. Help, please! We started out by listing all combinations of 5g weights with one other size of weight, and once we got through that, we moved up a size and repeated the process, but soon realized that there were many more combinations than we were going to be able to write out in a practical amount of time. Date: 10/07/2004 at 22:33:30 From: Doctor Greenie Subject: Re: Number of possible combinations of weights Hello, Sean. This problem is made easier by the fact that it asks you to determine how many ways there are rather than asking to list all the possible ways. In my mind, there are two keys to finding the answer to this question efficiently. (1) We will use a "greedy" algorithm - that is, we will use the largest number of largest weights possible at every stage. (2) Note that, if we have a solution involving one or more 15g weights, we can always replace each of the 15g weights with three 5g weights to get a different solution. The effect of this is that we only need to consider the 50g, 25g, and 15g weights to find the answer to the problem. We use the greedy algorithm to start our search--we use as many of the 50g weights as possible. We can only use at most one; two 50g weights is more than the 85g total we want. So the number of 50g weights is either 1 or 0; according to the greedy algorithm, we examine the cases with one 50g weight first. With one 50g weight, we need another 35g to make our target of 85g. Using an analysis similar to the preceding analysis, if we have one 50g weight then the number of 25g weights we can have is either 1 or 0. Again, using the greedy algorithm, we consider the case of one 50g and one 25g weight first. With this combination, we have 75g, so we need 10g more. That means we can't use any 15g weights; the remaining weight must be made using 5g weights. We begin a table summarizing our results.... column A: numbers of 50g and 25g weights column B: possible numbers of 15g weights with this combination of 50g and 25g weights column C: number of different solutions with this combination of 50g and 25g weights A B C --------------------- (1;1) 0 1 We have completed the analysis for the case where we have one each of the 50g and 25g weights; according to our greedy algorithm, we next analyze the case with one 50g weight and no 25g weights. With one 50g weight and no 25g weights, we need 35g more. We can use as many as two 15g weights. According to (2) above, that means we can use either 2, 1, or 0 15g weights, with whatever remains being made up of 5g weights. So now our summary table looks like this: A B C --------------------- (1;1) 0 1 (1;0) 0-2 3 According to our greedy algorithm, we have determined all the ways of making the 85g total using at least one 50g weight, so now we begin considering cases where the largest weights we use are the 25g weights. With a desired total of 85g, we can use up to three 25g weights; so we are going to consider cases where we have 3, 2, 1, or 0 25g weights. This analysis will finish our problem. -- no 50g weights; three 25g weights We have only 10g left; the number of 15g weights must be 0 -- no 50g weights; two 25g weights We have 35g left; the number of 15g weights can be 2, 1, or 0 -- no 50g weights; one 25g weight We have 60g left; the number of 15g weights can be 4, 3, 2, 1, or 0 -- no 50g weights; no 25g weights We have the entire 85g left; the number of 15g weights can be 5, 4, 3, 2, 1, or 0 And we can now finish our table and find the final answer to the problem: A B C -------------------- (1;1) 0 1 (1;0) 0-2 3 (0;3) 0 1 (0,2) 0-2 3 (0;1) 0-4 5 (0;0) 0-5 6 -------------------- total # of ways: 19 I hope this helps. Please write back if you have any further questions about any of this. - Doctor Greenie, The Math Forum http://mathforum.org/dr.math/ Date: 10/08/2004 at 10:59:43 From: Sean Subject: Thank you (Number of possible combinations of weights) Thanks Dr. Greenie!! You rock :) We finally did go through all the combinations, and wound up with 19 as well. Interestingly enough, if we divide each weight size by 5, the smallest weight, and add the resultants, they equal 19. Coincidental to be sure, but still quirky. |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/