1742.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include <stdio.h>
#include <memory.h>
#include <algorithm>
#define min(a,b)  (((a)<(b))?(a):(b))
using namespace std;
struct coin_type
{
	int a,c;
}coin[101];
int n, m;
int use[100001];
bool sign[100001];
int q[100001], qn;

bool cmp( coin_type s1, coin_type s2 )
{
	return  s1.a > s2.a;
}

bool init()
{
	int i;

	scanf( "%d %d", &n, &m );
	if( n == 0 && m == 0 ) return false;

	for( i=0; i<n; i++ )
	scanf( "%d", &coin[i].a );

	for( i=0; i<n; i++ )
	scanf( "%d", &coin[i].c );

	memset( sign, 0, sizeof( sign ) );
	memset( use, 0, sizeof( use ) );

	sort( coin, coin+n, cmp );

	return true;
}


int main()
{
	int i, h, j, v, c, temp, k;
	while( init( ) )
	{
		qn = 1;	q[0] = 0;
		
		sign[0] = true;

		for( i=0; i<n; i++ )
		{
			v = coin[i].a;
			c = coin[i].c;
			h = qn;

			for( j=0; j<qn; j++ )
			{
				k = q[j];
				temp = q[j] + v;
				if( temp <=m && !sign[temp] && use[k] < c )
				{
					sign[temp] = true;
					use[temp] = use[k] + 1;
					q[qn++] = temp;
				}
			}

			for( j=h; j<qn; j++ )
				use[q[j]] = 0;
		}

		printf( "%d\n", qn-1 );
	}
	return 0;
}