hello guys,
Can anybody solve the following coin changing and knapsack problem?
[coin change] Let {c1, c2, …., cn=1} be a set of distinct coin types,
where each ci is an integer. Each type is available in unlimited
quality. The coin changing problem is to make up an exact amount M
using a minimum total number of coins.
[0/1 knapsack] Given n objects, each has a weight wi and a profit pi,
and a knapsack with a capacity of M. This problem is to obtain a
filling of the knapsack that maximizes the total profit. Note that an
object Is either included or not included in the knapsack.
Show that the coin changing problem is polynomially reducible to the
0/1 knapsack problem.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
