### X-O__O-X's blog

By X-O__O-X, history, 5 months ago, I know how to solve the following variation;

Given list of coins c, c, ..., 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 wonder 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...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, I would like to know generally how one prove that DP cannot solve some problem, if possible ?

Thanks for reading Comments (10)
 » Obviously this can be solved with DP. Just create an array with $a_i$ copies of $c_i$ for each $i$ and do a standard DP. The running time here depends on the constraints for $c_i$.
•  » » 5 months ago, # ^ | ← Rev. 2 →   Yes but the standard DP I know involves distinct coins. If c = {1, 3, 1, 4} for example and we have 1 unit of each coin. how to count the number of unique ways to form 8. for example, 1 + 3 + 4 = 3 + 1 + 4 consider same way. My question is are sure if we have coins like 1,1,3,3,4 (sorted) we can apply same solution applied on distinct coins ?
•  » » » 5 months ago, # ^ | ← Rev. 2 →   The Dp I'm talking about is almost the same. You can process the coins of the same kind at the same time, something like this:$dp(W, i)$: number the number of ways of getting sum $W$ by using coins of type $\le i$. Now we are going to move to the $(i+1)-th$ type of coin. You can use from $0$ to $a[i+1]$ coins of this kind; if you use $k$ then you move to the state $dp(W + k\cdot c[i+1], i+1)$.Also, I recommend you to read this article. There, there are solutions to several variations of this problem (including some more efficient solutions to this particular problem).
•  » » » » ~~~~~ class Solution { public: int change(int amount, vector& coins) { int n = coins.size(); vector> dp(n+1, vector(amount+1)); for (int i=0; i<=n; ++i) dp[i] = 1; for (int i=1; i<=n; ++i) { for (int j=1; j<=amount; ++j) { /******/ int x = 0; while (j - x * 1ll * coins[i-1] >= 0) { dp[i][j] += dp[i-1][j - x * coins[i-1]]; ++x; } /******/ } } return dp[n][amount]; }};~~~~~You mean I will only need to add the condition x<=a[i] to while loop in this code which solve the problem when having inf. coins.Indeed. how stupid my question!Thank you.
•  » » » » » Yes, something like that.
•  » » No need to do dp, just do a greedy, sort the coins and take the coins from the start until u reach the target sum.
•  » » » What are u talking about? The problem is asking counting the number of ways of getting a sum. Moreover, the greedy you are saying (I guess for minimizing something) doesn’t always work.
•  » » » » i misread the problem but it is easy to see the greedy would work to see if we can make a change.
•  » » » » » Oh no. Imagine a coin with value 1, a coin with value 2, a coin with value 3, and a coin with value 6, and you wanna get sum 5. Your algorithm will say that it’s impossible, but indeed it is possible by taking the coin with value 3 and the one with value 2.
 » Not the same thing but this blog may help: https://petr-mitrichev.blogspot.com/2011/07/integral-bounded-knapsack-problem.html?m=1