Solving Subset Sum Counting: How to Make £2 from Coins

In summary, the conversation is about finding the number of ways to make £2 using coins with values of 200, 100, 50, 20, 10, 5, 2, and 1, without considering the order. The person has no idea how to solve it and has thought about a recursive solution and generating functions as potential approaches.
  • #1
martix
163
1

Homework Statement


How many different ways can £2 be made using any number of coins?
(In other words, how many ways can you obtain the sum of 200 with terms from the following finite set - 200, 100, 50, 20, 10, 5, 2, 1. Order does not matter.)

Homework Equations


None?


The Attempt at a Solution


No idea.
I've been mulling over this problem for way too much time now without producing anything viable.
A PnP solution is beyond me at this point. On the computational side I've been thinking of a recursive solution which should spawn this massive recursion tree and I'm pretty sure there's got to be a better method out there.
 
Physics news on Phys.org
  • #2
Do you know generating functions??
 
  • #3
Nope...
First time I've heard of those. I can always read up on them if they are relevant to the solution.
 

1. How does subset sum counting work?

Subset sum counting is a mathematical problem that involves finding all possible combinations of a given set of numbers that add up to a specific target value. In the case of making £2 from coins, the set of numbers would be the different denominations of coins and the target value would be £2. The goal is to find all the unique combinations of coins that add up to £2.

2. What is the significance of solving subset sum counting for making £2 from coins?

Solving subset sum counting for making £2 from coins has practical applications in everyday life. For example, it can help in counting and organizing loose change or in making change for larger bills. It also has implications in the field of computer science, where it is used in optimization problems and cryptography.

3. What is the most efficient approach to solving subset sum counting for making £2 from coins?

The most efficient approach to solving subset sum counting is through dynamic programming. This involves breaking down the problem into smaller subproblems and using a table to store the solutions to these subproblems. This allows for a faster and more efficient way of finding the desired combinations of coins that add up to £2.

4. Is there a limit to the number of coins that can be used in solving subset sum counting?

No, there is no limit to the number of coins that can be used in solving subset sum counting. The algorithm can be applied to any set of numbers, including a large number of coins. However, the time and resources required to find all possible combinations may increase as the number of coins increases.

5. Are there any practical uses for solving subset sum counting other than making £2 from coins?

Yes, there are many practical uses for solving subset sum counting. It can be applied to various types of optimization problems, such as scheduling and resource allocation. In cryptography, it is used in the design of secure encryption algorithms. It also has applications in other fields such as genetics, economics, and chemistry.

Similar threads

How many ways to count to 20 with positive integers and x > 3?
    • Calculus and Beyond Homework Help
Replies
22
Views
2K
Calculus 2 for Engineers: Riemann sums
    • Calculus and Beyond Homework Help
Replies
6
Views
1K
Combinatorics -- Counting Sets of Binary Strings
    • Calculus and Beyond Homework Help
Replies
3
Views
2K
I Solve Coin Sum Problem: Find Combinations for 200p
    • Linear and Abstract Algebra
Replies
13
Views
1K
How many number of IP addresses are available?
    • Calculus and Beyond Homework Help
Replies
2
Views
2K
Finding the Number of Terms Needed to Approximate an Infinite Sum within 1/100
    • Calculus and Beyond Homework Help
Replies
10
Views
2K
Sets and Counting: Drug Relief Study Results
    • Calculus and Beyond Homework Help
Replies
2
Views
7K
Solve Riemann Sum Question for Area Under Curve
    • Calculus and Beyond Homework Help
Replies
8
Views
2K
Number of onto functions from 2 sets
    • Calculus and Beyond Homework Help
Replies
10
Views
5K
Combinatorics, Assigning Occurrence Numbers to Integers
    • Calculus and Beyond Homework Help
Replies
2
Views
1K

Hot Threads

Recent Insights

Back
Top