Given a set of N coins C
=
{
c
1
,
c
2
,
c
3
,
.
.
.
,
cN
}
and a monetary value M
>
0
,
find the smallest subset of C that can pay value K
(
without change
)
.
Note that in this problem, C can have duplicates, and a coin can be used only once.
Examples. C
=
{
1
,
1
,
4
,
2
0
,
2
0
,
2
1
,
2
5
,
4
0
}
M
=
4
5
Answer
=
{
2
0
,
2
5
}
M
=
1
3
2
Answer
=
{
1
,
1
,
4
,
2
0
,
2
0
,
2
1
,
2
5
,
4
0
}
M
=
3
Answer
=
No subset meets the requirements
Design a backtracking algorithm to solve this problem. Follow the steps below:
A
.
Draw a tree showing how a brute

force enumeration algorithm enumerates the solutions for the following instance: C
=
{
2
,
2
,
4
}
M
=
4
.
Clearly show on the tree what each node and edge represents and which solutions are feasible and which are not.
B
.
Suggest a backtracking strategy to improve the running time of the brute

force algorithm.
C
.
Provide an example of values for C
{
at least
4
}
and M that will lead to:
1
.
No pruning in the tree.
2
.
Maximum pruning in the tree.
A. Draw a tree showing how a bruteforce enumeration algorithm enumerates the solutions for the following instance: C = {2, 2, 4} M = 4.
B. Suggest a backtracking strategy to improve the running time of the bruteforce algorithm.
C. Provide an example of values for C {at least 4} and M that will lead to:
# 1. No pruning in the tree.
# 2. Maximum pruning in the tree.
Not the question you are looking for? Ask here!
Enter question by text
Enter question by image
Upgrade to Asksia Pro
Join a AskSia's Pro Plan, and get 24/7 AI tutoring for your reviews, assignments, quizzes and exam preps.