vikalp14's blog

How to write the memoisation function for this recurrence for the coin change problem?
By vikalp14, history, 6 years ago, In English

change(rs) gives the coins required for remaining value

  1. change(0) = 0 // we need 0 coins to produce 0 cents
  2. change(< 0) = ∞ // in practice, we can return a large positive value
  3. change(value) = 1 + min(change(value — coinValue[i])) ∀ i ∈ [0..n-1]

I wrote this but its not working (gives a large integer value !)


#define INT_MA 999999
int memo[1000],v[1000];
int coin(int rs)
{
	if(rs == 0)
		return 0;
	if(rs<0)
		return INT_MA;
	if(memo[rs] != INT_MA)
		return memo[rs];
	int &a = memo[rs];
	for(int i=0;i<n;i++)
	{
		a=min(a,coin(rs-v[i]));
	}
	if(a!=INT_MA)
	a=a+1;
	return a;
}
int main()
{
int n,val;
cin>>n>>val;

for(int i=0;i<n;i++)
cin>>v[i];

memset(memo,INT_MA,sizeof memo);
cout<<coin(val);
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
6 years ago, # |
← Rev. 8   Vote: I like it 0 Vote: I do not like it

The initialization of the memo array using the memset() function is incorrect.

void * memset ( void * ptr, int value, size_t num )

is a byte-based memory block filling library function. This means that any integer value passed to the second parameter of the function is converted to an unsigned char value before using it to fill the memory block bytes.

Just replace the line if(memo[rs] != INT_MA) with if( memo[rs] != -1 ), and replace the line memset(memo,INT_MA,sizeof memo); with memset( memo, -1, sizeof memo );. This should fix the problem.

The 16-bit, 32-bit, 64-bit, 128-bit, etc. memory representation of the integer value -1 is composed of 2, 4, 8, 16, etc. bytes, respectively, that contain the same unsigned char value 255, which is the equivalent value of the passed integer value -1 when only the least significant eight bits of its binary representation are used as an unsigned char value.

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

    Did that now getting 0 as result

    Because a=min(a,coin(rs-v[i]));

    When rs<v[i] the coin(rs-v[i]) will give INT_MA and a by default has the value a=-1

    So min(a,coin(rs-v[i])) = min(-1,INT_MA) which gives -1

    So now a=-1

    After loop ends a=a+1 ,hence a becomes a=0

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

      Initialise memo with -1, and after the int&a = line add a = INT_MAbefore the loop.

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

      I haven't checked the rest of the code. But the function should never have -1 as its return value, as this value is the initial value in the memoarray, and is used to indicate that the actual value has not been computed before.

      → Reply
»
6 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

The following is a C++14 Update to your code.

  1. The static int array is replaced with base class array< int, N > in a memo_t data structure. This allows the byte-based function memset() to be replaced with the integer-based initialization function array::fill().

  2. The function coins() is replaced with function min_count() in a coins_change_t data structure that inherits a base class set< int > to read the available set of coins from cin and store them in the set.

  3. The index-based loop is replaced with a compact loop for( auto v: *this ) inside the function.

  4. The constant INT_MA is replaced with the standard constant INT_MAX defined in the library header <climits>.

  5. The return value of the function min_change_t::min_count() is checked in the main program. If such value is equal to INT_MAX, the program outputs -1.

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

    Thanks this is the working code


    #include<bits/stdc++.h>
using namespace std;
int c[1000];
int v[1000];
int n;

int coin(int rs)
{
	if(rs == 0){
		return 0;
	}
	
	if(rs<0)
		return INT_MAX;

	if(c[rs] != -1)
		return c[rs];

	int &a = c[rs];
	a=INT_MAX;

	for(int i=0;i<n;i++)
	{
		a=min(a,coin(rs-v[i]));
	}
	a+=1;
	return a;
}

int main(){
	int rs;
	cin>>n>>rs;
	
	for(int i=0;i<n;i++)
	{
		cin>>v[i];
	}
	memset(c,-1,sizeof c);
	cout<<coin(rs);
}
    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If n = 0 it would overflow and return — INT_MAX.Else you're good.

      I always avoid using these max values, whether it's int or long long.You can choose big values that are close to them and at the same time won't cause any trouble.Like 2e9 for int and up to 9e18 in long long.Most likely you won't need them, but it's better than the actual maximum values, which will overflow if you add 1 to them.

      → Reply