DaniWeb Forum Index > Software Development > C++

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

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

•

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

#11

Oct 10th, 2008

Well, it's a good time to change notes:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
/// Must be coin[0] < coin[1] < ... < coin[n-1]
int NumberOfWays(int sum, const int coin[], int n) {
    if (0 >-- n)
        return 0;
    int high = coin[n];
    if (n == 0)
        return sum % high? 0: 1;
    int k = sum / high;
    int ways = 0;
    for (int i = 0; i <= k; ++i, sum -= high) {
        ways += NumberOfWays(sum, coin, n);
    }
    return ways;
}
 
int main()
{
    int coin[] = { 1, 2, 5, 25 };
    int n = sizeof coin / sizeof *coin;
    int ways, sum = 100;
    ways = NumberOfWays(sum,coin,n);
    std::cout << ways << std::endl;
    return 0;
}
// Output: 1042. Heaps of ways!..
/// Must be coin[0] < coin[1] < ... < coin[n-1]
int NumberOfWays(int sum, const int coin[], int n) {
    if (0 >-- n)
        return 0;
    int high = coin[n];
    if (n == 0)
        return sum % high? 0: 1;
    int k = sum / high;
    int ways = 0;
    for (int i = 0; i <= k; ++i, sum -= high) {
        ways += NumberOfWays(sum, coin, n);
    }
    return ways;
}

int main()
{
    int coin[] = { 1, 2, 5, 25 };
    int n = sizeof coin / sizeof *coin;
    int ways, sum = 100;
    ways = NumberOfWays(sum,coin,n);
    std::cout << ways << std::endl;
    return 0;
}
// Output: 1042. Heaps of ways!..

Absolutely supersonic code

...

•

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

#12

Oct 10th, 2008

hmm, okay...that's fast... reps to you!
//edit
umm it's not that fast, i see now, mine is alot faster, you haven't optimized the recursion, so you're making calls that aren't needed... mine goes fast for 10000, your is slow. :O?

Last edited by gregorynoob; Oct 10th, 2008 at 10:02 am.

•

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

#13

Oct 10th, 2008

OK, your code is faster.
No need in true recursion in this algorithm.
But I'm too lazy to 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

#14

Oct 10th, 2008

hehe, i'm lazy too, but i still wanna speed it up. found another way, without recursion, the idea is: no need to check for 1's, they always give 1, and 2's always give ( n/2 )+1...
still too slow

Last edited by gregorynoob; Oct 10th, 2008 at 11:17 am.

•

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

#15

Oct 10th, 2008

It's a brutal force method to enumerate all deals.
Let this tin with silicic stuffing works...

•

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

#16

Oct 10th, 2008

do you think the same thing when discussing algorithms with O(2^n) time complexity? poor tin cans would struggle for centuries if n was...say 100.

•

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

#17

Oct 10th, 2008

Of course, NP-complexity is a barrier. To be up against a blank wall?
But this alg is not k power n complexity (polynomial only).
Be careful with combinatory problems - that's all

•

Join Date: Jan 2008

Posts: 3,836

Reputation: VernonDozier has a reputation beyond repute

Solved Threads: 503

VernonDozier VernonDozier is offline

Offline

Senior Poster

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

#18

Oct 10th, 2008

•

Originally Posted by gregorynoob

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?

Take all of the % MOD lines out of there. They give you bad results (i.e. there are 43 ways to make 515) and they slow the program down.

Second, it's not an issue here because the smallest "coin" is 1, but this line is a problem if the smallest "coin" is, say, 2:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
if(m == 0 || n == 0) return  (dp[n][m] = 1);
if(m == 0 || n == 0) return  (dp[n][m] = 1);

If coins[] = {2, 3, 5, 25} or something similar where the smallest element is not 1, ret (1, 0) would equal 0 (no way to to make 1 from {2, 3, 5, 25}). Thus if this algorithm is meant to cover all coins arrays, that line would need to change since dp[n][0] sometimes will equal 0 and sometimes will equal 1 for varying n values. So if you want to allow for that, you'd also need to set the array with memset to some negative number rather than 0 ahead of time if you are checking to see whether the array value has been filled and you allow the smallest coin to be greater than one.