X-O__O-X's blog

Is this variation of coin change problem solvable using DP ?
By X-O__O-X, history, 4 years ago, In English

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

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 ?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        ~~~~~ class Solution { public: int change(int amount, vector& coins) {

        int n = coins.size(); 

    vector<vector<int>> dp(n+1, vector<int>(amount+1)); 

    for (int i=0; i<=n; ++i) dp[i][0] = 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.

        → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        i misread the problem but it is easy to see the greedy would work to see if we can make a change.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Not the same thing but this blog may help: https://petr-mitrichev.blogspot.com/2011/07/integral-bounded-knapsack-problem.html?m=1

→ Reply