Finding the whole combination of a number for a specific amount
Array A ={1,2,3}
For sum value = 5
Possible combination
{3,2} , {1,1,1,1,1} , {2,2,1} and all possiable one
here is my approach:
int count( int S[], int m, int n )
{
// m is the size of the array and n is required sum
// If n is 0 then there is 1 solution (do not include any coin)
if (n == 0)
return 1;
// If n is less than 0 then no solution exists
if (n < 0)
return 0;
// If there are no coins and n is greater than 0, then no solution exist
if (m <=0 && n >= 1)
return 0;
// count is sum of solutions (i) including S[m-1] (ii) excluding S[m-1]
return count( S, m - 1, n ) + count( S, m, n-S[m-1] );
}
My approach Disadvantage: . He has to recount many combinations over and over again. Thus, the value of the sum is very large, therefore it is very slow.
I want to implement this with dynamic programmingplease provide me with an explanation how I can save the calculated value so that I can reuse it and shorten my program time
source to share
I would do it differently:
-
create an array of coins to match the amount
- one type of coin
- start with the biggest
- add as many of them as possible.
- but the amount should be
<=
, then the target amount - if the final amount is reached, the result of saving
- recursively call step 1 for the next bottom coin
- but remember the last state of the coin array
- if there is no coin = 1, then sometimes the result will be invalid
- go to next combination
- restore the last state of the coin array
- remove the last coin from it
- if not, then stop
- else repeat step 2
- one type of coin
-
permutations of counting / combinations if and order matters
- so let's assume the result and rearrange it according to the rules of your problem.
- to get more solutions from him.
- it's faster than trying every opportunity in 1.
example (for 1.):
coins = { 5,2,1 } sum=7 5 | 2 5 | - | 1 1 - | 2 2 2 | 1 - | 2 2 | 1 1 1 - | 2 | 1 1 1 1 1
-
|
separates the recursive layer - there is one level of recursion for each coin type
- so you will need memory for the three states of the array in this case (length depends on the target sum)
- this is acceptable (I've seen solutions with much more complex space complexity for this problem)
- for very large amounts, I would use RLE to save memory and speed things up.
[edit1] C ++ source code
//---------------------------------------------------------------------------
void prn_coins(int *count,int *value,int coins) // just to output solution somewhere
{
int i;
AnsiString s="";
for (i=0;i<coins;i++)
s+=AnsiString().sprintf("%ix%i ",count[i],value[i]);
Form1->mm_log->Lines->Add(s);
}
//---------------------------------------------------------------------------
void get_coins(int *count,int *value,int coins,int sum,int ix=0,int si=0)
{
if (ix>=coins) return; // exit
if (ix==0) // init:
{
ix=0; // first layer
si=0; // no sum in solution for now
for (int i=0;i<coins;i++) count[i]=0; // no coins in solution for now
}
//1. genere actal coint type value[]
count[ix]=(sum-si)/value[ix]; // as close to sum as can
si+=value[ix]*count[ix]; // update actual sum
for(;;)
{
//2. recursion call
if (si==sum) prn_coins(count,value,coins);
else get_coins(count,value,coins,sum,ix+1,si);
//3. next combination
if (count[ix]) { count[ix]--; si-=value[ix]; }
else break;
}
}
//---------------------------------------------------------------------------
void main()
{
const int _coins=3; // coin types
int value[_coins]={5,2,1}; // coin values (must be in descending order !!!)
int count[_coins]={0,0,0}; // coin count in actual solution (RLE)
get_coins(count,value,_coins,7);
}
//-------------------------------------------------------------------------
- this code took ~ 3ms on my HW setup
- just change the prn_coins function to your print form (I used the VCL and AnsiSring note)
- in this code, the state of the solution is automatically overwritten to the previous state.
- so there is no need for further memoize (otherwise the count array would have to be copied before and after the recursion)
- Now a permutation step will be necessary if:
- is each coin unique? (1 1 2 5)! = ( 1 1 2 5)
- or just the type of coin? (1 1 2 5)! = (1 2 1 5)
- in this case, just add the permutation code to the prn_coins function ...
- but that's another question ...
source to share
A very simple change to your solution would be to just add "memoization".
Given that the array is S
fixed, the result of your function depends on m
and n
. Therefore, you can make the following small change:
int count( int S[], int m, int n ) {
...
if (cache[m][n] == -1) {
cache[m][n] = count( S, m - 1, n ) + count( S, m, n-S[m-1] );
}
return cache[m][n];
}
This way you compute the result once for each distinct pair of values m
and n
.
The idea is to keep the 2d array indexed ( m
, n
), all initialized to -1
(which means "not yet computed"). When you are about to compute the value in count
, you first check if the value has not yet been computed, and if so, you store the result in a 2d matrix as well, so as not to repeat the same number again in the future.
source to share
For dynamic programming, you need to generalize your problem. Let be S(a, x)
all possible sums of a value x
, only using the values from A
, starting with the index A
. Your original problem is S(0, X)
.
Since you have a discrete function with two parameters, you can store its results in a 2d array.
There are some simple cases: there is no solution for a = A.length
and X > 0
.
There is a set containing only an empty amount for X = 0
.
Now you have to find a recursive formula for other cases and populate the table so that the indexes you depend on have already been calculated (hint: consider a loop back).
source to share