Is this variation of coin change problem solvable using DP ?

Правка en1, от X-O__O-X, 2020-12-03 18:37:11

I know how to solve the following variation;

Given list of coins c[1], c[2], ..., c[n], no 2 coins are same, and a target sum. Count number of ways to make the sum using the given coins ?

When

  • There is 1 unit of each coin

  • There is infinite supply of each coin.

I wander what if there is a specific amount for each type of coin. so I am given the list of types of coins and the list a[1]...a[n] such that a[i] is the number of coins allowed of type c[i].

Can we solve it using DP ?

If yes, is the solution similar to the solution of the classical problem ? appreciate if you describe the whole solution.

If no, how to solve it? at least, what topics or techniques required?

Also, would like to know generally how one prove that DP cannot solve some problem, if possible ?

Thanks for reading

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский X-O__O-X 2020-12-03 18:42:06 4
en1 Английский X-O__O-X 2020-12-03 18:37:11 897 Initial revision (published)