UVa-11517 : Exact Change

問題概要

コインがN(<100)枚ある。価値はV[i](<10^4)である。コインを使って作れるT(<10^4)以上の最小金額と、それに必要な最小枚数を求める問題。

解法

(何枚目まで見た、いくら)を組にして必要な最小枚数でDP。よくある01ナップザック。

acceptされたコード

計算量O(T*N)。

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

const int MAX_N = 100;
const int MAX_V = 10000;
const int INF = 1<<29;

int N, V;
int as[MAX_N];
int dp[MAX_N+1][2*MAX_V];

void init(){
	scanf("%d%d", &V, &N);
	for(int i=0; i<N; i++){
		scanf("%d", as + i);
	}
	for(int i=0; i<=N; i++){
		fill(dp[i], dp[i] + 2*MAX_V, INF);
	}
}

void solve(){
	dp[0][0] = 0;

	for(int i=0; i<N; i++){
		for(int v=0; v<2*MAX_V; v++)if(dp[i][v] < INF){
			dp[i+1][v] = min(dp[i+1][v], dp[i][v]);
			int tar = v + as[i];
			if(tar <= MAX_V){
				dp[i+1][tar] = min(dp[i+1][tar], dp[i][v] + 1);
			}
		}
	}

	for(int j=V; j<2*MAX_V; j++)if(dp[N][j] < INF){
		printf("%d %d\n", j, dp[N][j]);
		return ;
	}
}

int main(){
	int T;
	scanf("%d", &T);
	while(T--){
		init();
		solve();
	}

	return 0;
}