nafeeur10's blog

Help: Coin Change-LightOJ:1233 — Coin Change (III)
By nafeeur10, 10 years ago, In English

Coin Change(III) I want to solve it by three state coin change DP. But I am getting MLE, RTE. How can I solve it by this way?? Please help me. My code is here.

#include <bits/stdc++.h>

using namespace std;

int n,m,dp[101][101][1001];
int coin[101], number_coin[101];
set<int>S;
int M;

int call(int i, int taken_i, int make)
{
    if(make>=1 && make<=M) S.insert(make);
    if(make>M || i>n) return 0;
    if(make==M) return 1;

    if(dp[i][taken_i][make]!=-1)
        return dp[i][taken_i][make];
    int p1=0, p2=0;
    if(taken_i>0)
    {
        p1=call(i,taken_i-1,make+coin[i]);
    }
    p2=call(i+1,number_coin[i+1], make);
    dp[i][taken_i][make]=p1+p2;
    //cout<<dp[i][taken_i][make]<<endl;
    return dp[i][taken_i][make];
}

int main()
{
    int t;
    scanf("%d",&t);
    int cas=0;
    while(t--)
    {
        scanf("%d %d",&n, &m);
        M=m;
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&coin[i]);
        }
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&number_coin[i]);
        }

        memset(dp,-1,sizeof(dp));
        int a=call(1,number_coin[1],0);
        printf("Case %d: %d\n",++cas,S.size());
        S.clear();
    }
    return 0;
}
  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you please tell what is this problem about? I cant open LightOJ

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

Sorry, undertansder bad the problems!!!

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

I think an O(M*N*T) solution could pass. The idea is just to maintain an array dp[current sum][2], where dp[s][i&1] += dp[s-x*a[i]][(i-1)&1] for every 0 <= x <= c[i]. But this solution is O(M*N*T*C[i]). But we can reduse it to O(N*M*T). We will maintain an array pref[current sum]. pref[s] = dp[s] + pref[s-a[i]]. So then dp[s]=pred[s]. Or simply we can change the formula to dp[s][i&1]=dp[s][(i-1)&1] + dp[s-a[i]][i&1].

P.S. if you dont know a&1 is the same as a%2.

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

    Or simply we can change the formula to dp[s][i&1]=dp[s][(i-1)&1] + dp[s-a[i]][i&1].

    I think that dp [s] [i&1] = dp [s] [(i-1)&1] + dp [s-a[i]] [i&1] is correct only if c[i] is unlimited because in your recurrence dp[s][i] depends on dp [s-a[i]] [i] which depends on dp [s-2*a[i]] [i] which itself depends on dp [s-3*a[i]] [i]. So dp [s][i&1] depends on dp [s-(c[i]+1)*a[i]] [i&1] too. Am I wrong?

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

      Didn't realize that :d. Then I think it must be dp[s][i&1]=dp[s][(i-1)&1] + dp[s-a[i]][i&1] -dp[s-a[i]*c[i]][(i-1)&1].

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

        Actually I am not understanding your talking. If you help me based on my code then it will be helpful for me. Please.

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

Send the link to the condition of the problem

→ Reply
»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Hey!! I am suggesting you the procedure I've followed!! Hope, it helps!!

This problem can be solved in O(n*m) time. where n=number of coins, m=amount.

Suppose, I want to check the money between 1 to 6. I have coins 2,3. 2 can be used for 2 times.

The moneys are 1,2,3,4,5,6,7,8,9. Suppose I want to start with coin 2. then I'll iterate through 2 to 9 to check which money I can make with this coin. Initially, You set dp[0]=1.//base case.

So, for 2 , starting from i=2, I can make 2 since dp[2-[present_coin]]==1, i.e, dp[0]=1. then set dp[2]=present coin.//since number of coins are limited, u will need this to check. now store 1 in an array since this is the 1st use of coin 2. _cnt array will store how many times a particular coin has been used to make a amount.

so, dp[2]=2. _cnt[2]=1.

now, for i=3, I can't make 3 since dp[3-[present_coin]]==0,i.e, dp[1]=0 and I couldn't make 1. then leave it. dp[3]=0. _cnt[2]=0.

for i=4, I can make 4 since dp[4-present_coin]==2, i.e dp[2]=2. Here is a matter, since dp[4-present_coin]==2 that means coin 2 has been made with a use of present coin. Since number of coins is limited so you have to check _cnt array to determine whether you can use present coin or you have already used max time.

since _cnt[2]=1 that means you have used present coin 1 time to make previous amount,2. and if you want to make 4 using present coin then you will used present coin for _cnt[2]+1=2 times.Since I can use coin 2 for max 2 times so, I can use present coin to make 4. dp[4]=2. _cnt[4]=_cnt[2]+1.//1 for using present coin another time.

Now, for i=5, I can't make 5 since dp[5-[present_coin]]==0,i.e, dp[3]=0 and I couldn't make 5 using present coin since coin 3 has not been made yet; then leave it. dp[5]=0. _cnt[5]=0.

For i=6, I can make 6 since dp[6-present_coin]==2, i.e dp[4]=2. Here is a matter, since dp[6-present_coin]==2 that means coin 4 has been made with a use of present coin. Since number of coins is limited so you have to check cnt array to determine whether you can use present coin or you have already used max time. Since cnt[4]=4 that means you have used present coin 2 times to make previous amount,4. and if you want to make 6 using present coin then you will used present coin for _cnt[4]+1=3 times,which is not allowed.Since I can use coin 2 for max 2 times so, I can't use present coin to make 6. dp[6]=0. _cnt6]=0.

The last case, i=6, is very important to understand.

→ Reply