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 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[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, I would like to know generally how one **prove** that DP cannot solve some problem, if possible ?

Thanks for reading

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$$$.

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 ?

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) {

};~~~~~

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