Finding a Combination of Coins with dollar amount ceiling

Question

The scenario is this: There are 50 coins in a bag of the following denominations:

50 cent pieces: 5
25 cent pieces: 10
10 cent pieces: 15
5 cent pieces: 20

You can choose five coins from the bag (without replacement). Order does not matter. Total combinations is 50 choose 5, or 2,118,760, but how many combinations are there where the total is less than $1? Combinations of four or fewer coins are not allowed. You must choose five coins.

Examples:

50 Cent, 25 Cent, 5 cent, 10 cent, 5 cent - GOOD
50 Cent, 25 Cent, 25 cent, 10 cent, 10 cent - NO GOOD

Can this be done using Excel? I want to first generate a list of all of the combinations and then eliminate those results less than $1, but I don't see any way to do that.

Would I be better off using a program other than excel?

No I'm studying basic combinations vs permutations which are easier. I'm just curious if there is a way to figure out a problem like this. I made up the amounts — Jake Green, Sep 24 '15 at 23:07
It's *less* than $1, not exactly $1. Even five nickels satisfies the constraint. — Prune, Sep 24 '15 at 23:17
@Prune exactly. They probably weren't the right denominations to pick for this example. My question was really about how would one go about eliminating combinations based on another variable or governor. 50-50-*-*-* would always be out for example. I've never heard of recursion, but sounds like Python is what I have to learn — Jake Green, Sep 24 '15 at 23:32
I don't think recursion is the best way to solve this: just loop through choosing the five coins, making each legal choice once (which is a loop inside the choose-five-times loop). — Prune, Sep 24 '15 at 23:37
An [example](http://stackoverflow.com/questions/31454110/the-brute-force-method-using-vba-for-solving-an-equation-with-nine-unknown-varia) to do permutations in excel. — findwindow, Sep 24 '15 at 23:47

score 0 · Answer 1 · answered Sep 24 '15 at 23:24

First of all, you have at least five coins of each type, so there is no restriction on quantity of each denomination. You can choose any of the four denominations with each choice. Therefore, you have only 4^5 permutations to consider.

The simplest way in Python would be to set up your choice list of [50, 25, 10, 5]. Loop through the possible choices to make lists of 5 coins in non-increasing order (choice position cannot be less than the previous one).

At each coin choice, check sum(list_so_far); if >= 100, continue.

At the end of each list of 5, append the survivor to your list of solutions.

Does this get you moving well enough? We try not to serve as a code-writing service. I hope that this attack is within your programming capabilities.

Thane Plummer · Accepted Answer · 2015-09-25T13:35:50.913

If you're studying permutations vs. combinations, take a look at the itertools library, and you'll find functions for both that operate on an enumerable sequence.

import itertools

fifties = [50 for i in range(5)]
twentyfives = [25 for i in range(10)]
tens = [10 for i in range(15)]
fives = [5 for i in range(20)]
bag = fifties + twentyfives + tens + fives
allcombinations = itertools.combinations(bag, 5)
less_than = [comb for comb in allcombinations if sum(comb) < 100]

Finding a Combination of Coins with dollar amount ceiling

2 Answers2