POJ-1742, TJU-3320 : Coins

問題概要

N(<100)種類のコインがある。価値がA[i](<10^5), 枚数がC[i](<10^3)枚ある。これらを用いて作ることのできる金額の種類は[1..M](M<10^5)に何枚あるか求める問題。

解法

蟻本p.62と同じ。
計算量O(N*M)。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_N = 100;
const int MAX_M = 100000;

int dp[2][MAX_M + 1];
int N, M;
int as[MAX_N], cs[MAX_N];

bool init(){
	scanf("%d%d", &N, &M);
	if(N==0 && M==0){
		return false;
	}

	for(int i=0; i<N; i++){
		scanf("%d", as+i);
	}

	for(int i=0; i<N; i++){
		scanf("%d", cs+i);
	}

	return true;
}

int solve(){
	int *cur, *nxt;
	memset(dp, -1, sizeof(dp));
	cur = dp[0];
	nxt = dp[1];
	cur[0] = 0;

	for(int i=0; i<N; i++){
		memset(nxt, -1, sizeof(dp[0]));
		for(int j=0; j<=M; j++){
			if( cur[j] >= 0 ){
				nxt[j] = cs[i];
			}
			else if( as[i] <= j && nxt[j - as[i]] >= 1){
				nxt[j] = nxt[j - as[i]] - 1;
			}
		}
		swap(cur, nxt);
	}

	int ans = 0;
	for(int i=1; i<=M; i++){
		if(cur[i] >= 0){
			ans++;
		}
	}

	return ans;
}

int main(){
	while( init() ){
		printf("%d\n", solve());
	}

	return 0;
}