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; }