DaniWeb Forum Index > Software Development > C++

C++ RSS

number of ways to..ehh, i hate counting ways

Please support our C++ advertiser: Intel Parallel Studio Home

•

Join Date: Jun 2008

Posts: 86

Reputation: gregorynoob is an unknown quantity at this point

Solved Threads: 5

gregorynoob gregorynoob is offline

Offline

Junior Poster in Training

number of ways to..ehh, i hate counting ways

Oct 8th, 2008

okay, this is the problem (variation of the knapsack coins problem): you've got 4 coin types:
1 cent, 2 cents, 5 cents and a quarter...infinite amount of each. I'm supposed to find the number of ways in which the coins can be arranged to form the sum of some integer n...
well i... had an idea but it proved pretty wrong.
my idea was to check all the possible ways of forming n with two other numbers, and save the solution as number of needed for the first times number of needed for the second, the problem is it is not always the case, as you can get large numbers cause of repetitions, for example 6:
2 + 4
two ways to make 2 ( 2, 1+1 )
three ways to make 4( 2+2, 1+1+1+1, 2+1 )
multiplied... 6 ways? nope...5
1+1+1+1+1+1
2+1+1+1+1
2+2+1+1
2+2+2
5+1... damn...

•

Join Date: Jul 2008

Posts: 2,001

Reputation: ArkM has much to be proud of

Solved Threads: 343

ArkM

Offline

Postaholic

Re: number of ways to..ehh, i hate counting ways

Oct 8th, 2008

Fortunately, no need to count ways yourself. Let a dumb computer do that

...

•

Join Date: Jun 2008

Posts: 86

Reputation: gregorynoob is an unknown quantity at this point

Solved Threads: 5

gregorynoob gregorynoob is offline

Offline

Junior Poster in Training

Re: number of ways to..ehh, i hate counting ways

Oct 8th, 2008

hmm, yeah, but how can it be done in some reasonable time?

•

Join Date: Jul 2008

Posts: 2,001

Reputation: ArkM has much to be proud of

Solved Threads: 343

ArkM

Offline

Postaholic

Re: number of ways to..ehh, i hate counting ways

Oct 8th, 2008

As usually: by solutions space reduction. Start from the largest coin type then recursively arrange the rest of sum with smaller set of coins and so on. Count all good solutions (with multiply and add operators

)...

•

Join Date: Jun 2008

Posts: 86

Reputation: gregorynoob is an unknown quantity at this point

Solved Threads: 5

gregorynoob gregorynoob is offline

Offline

Junior Poster in Training

Re: number of ways to..ehh, i hate counting ways

Oct 8th, 2008

hmmm, could i please get a more detailed explanation?

•

Join Date: Jun 2008

Posts: 86

Reputation: gregorynoob is an unknown quantity at this point

Solved Threads: 5

gregorynoob gregorynoob is offline

Offline

Junior Poster in Training

Re: number of ways to..ehh, i hate counting ways

Oct 8th, 2008

i mean, for example 3 has 2 solutions: 1+1+1 and 2+1, so if i go your way, i'll first take 2 off of the once and run the recursion on 3-2=1
which will give 1 solution. then i'll go down to 1, and run recursion on 3-1=2, and2 will give me 2 solutions: 1+1, 2... so i end up with 3?

•

Join Date: Jul 2008

Posts: 2,001

Reputation: ArkM has much to be proud of

Solved Threads: 343

ArkM

Offline

Postaholic

Re: number of ways to..ehh, i hate counting ways

Oct 8th, 2008

Nope. You have troubles with integer arithmetics.
For two cent coin: possible 0 or 1.
1st case: 3 - 0 = 3, for 1 cent coins 1 solution (1+1+1); 1 solution subtotal
2nd case: 3 - 2 = 1, for 1 cent coin 1 solution (1); 1 solution subtotal
1 + 1 = 2 - 2 solutions total, that's OK.
It is understandable that you hate counting

...

Last edited by ArkM; Oct 8th, 2008 at 6:37 pm.

•

Join Date: Jun 2008

Posts: 86

Reputation: gregorynoob is an unknown quantity at this point

Solved Threads: 5

gregorynoob gregorynoob is offline

Offline

Junior Poster in Training

Re: number of ways to..ehh, i hate counting ways

Oct 9th, 2008

lol, i get it now finally... i thought i'm supposed to go from the largest coin down every time...that would be just sick.

•

Join Date: Jun 2008

Posts: 86

Reputation: gregorynoob is an unknown quantity at this point

Solved Threads: 5

gregorynoob gregorynoob is offline

Offline

Junior Poster in Training

Re: number of ways to..ehh, i hate counting ways

Oct 9th, 2008

hmm, well now i've implemented it, but it's so damn slow... it should work fast for 100k atleast... here's my implementation:

 Help with Code Tags 
 c++ Syntax (Toggle Plain Text) 
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MOD 100000
using namespace std;
 
const int coins[] = {1, 2, 5, 25};
 
int n, dp[100000][5];
 
int rec(int n, int m) {
    int ret = 0; if(dp[n][m]) return dp[n][m];
    if(m == 0 || n == 0) return  (dp[n][m] = 1);
    if(n < coins[m]) return (rec(n, m-1)); 
    for(int i = 0; i*coins[m] <= n; ++i) {
         ret = ((ret%MOD) + (rec(n-i*coins[m], m-1)%MOD))%MOD;
    }
    return (dp[n][m] = ret);
}
 
int main( void )
{
    scanf("%d", &n);
 
    memset(dp, 0, sizeof dp);
    printf("%d\n", rec(n, 3)%MOD);
 
    return 0;
}
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MOD 100000
using namespace std;

const int coins[] = {1, 2, 5, 25};

int n, dp[100000][5];

int rec(int n, int m) {
    int ret = 0; if(dp[n][m]) return dp[n][m];
    if(m == 0 || n == 0) return  (dp[n][m] = 1);
    if(n < coins[m]) return (rec(n, m-1)); 
    for(int i = 0; i*coins[m] <= n; ++i) {
         ret = ((ret%MOD) + (rec(n-i*coins[m], m-1)%MOD))%MOD;
    }
    return (dp[n][m] = ret);
}

int main( void )
{
    scanf("%d", &n);
    
    memset(dp, 0, sizeof dp);
    printf("%d\n", rec(n, 3)%MOD);
    
    return 0;
}

i guess my implementation is stupid in some way... or can it run no faster?

Last edited by gregorynoob; Oct 9th, 2008 at 3:54 pm.

•

Join Date: Jul 2008

Posts: 2,001

Reputation: ArkM has much to be proud of

Solved Threads: 343

ArkM

Offline

Postaholic

Re: number of ways to..ehh, i hate counting ways

#10

Oct 9th, 2008

Sorry, I have no time to inspect your implementation carefully, but no need in arrays in this algorithm (except coins which must be a parameter of a recursive function). No need in <algorithm> header or MOD macros too.
It must be a very fast (and short) code...

Last edited by ArkM; Oct 9th, 2008 at 8:55 pm.