Блог пользователя vikalp14

How to write the memoisation function for this recurrence for the coin change problem?
Автор vikalp14, история, 8 лет назад, По-английски

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);
}
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
8 лет назад, скрыть # |
← Rev. 8  
Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
8 лет назад, скрыть # |
← Rev. 4  
Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    8 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +1 Проголосовать: не нравится

    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);
}
    → Ответить
    • »
      »
      »
      8 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить