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

[gregorynoob]

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

[ArkM]

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

[gregorynoob]

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

[ArkM]

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

[gregorynoob]

hmmm, could i please get a more detailed explanation?

[gregorynoob]

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?

[ArkM]

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

[gregorynoob]

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.

[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:

#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?

[ArkM]

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

[ArkM]

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

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

[gregorynoob]

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?

[ArkM]

OK, your code is faster.
No need in true recursion in this algorithm.
But I'm too lazy to do that ;)...

[gregorynoob]

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 :(

[ArkM]

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

[gregorynoob]

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.

[ArkM]

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

[VernonDozier]

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

#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:

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.