UVA – 166 – Coin Change

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
int coin[6] = { 5, 10, 20, 50, 100, 200 };
int stock[6];
int best[505];
int dollars, cents;
int dp[505][6];
int INF = 1 << 29, taken=0;
int getMin(int amount, int i) {
if (amount < -500) return INF;
if (i < 0 )
if (amount <= 0) return best[-amount];
else return INF;

if (!stock[i]) return getMin(amount, i - 1);
if(dp[amount][i]!= INF) return dp[amount][i];

stock[i]-= 1, taken = getMin(amount - coin[i], i) + 1, stock[i]+=1;
return (dp[amount < 0 ? -amount : amount][i] = min(taken,  getMin(amount, i - 1)));
}

int main() {

for (int amount = 0; amount < 505; amount++) {
best[amount] = INF;
for (int j = 0; j < 6; j++)
dp[amount][j] = INF;
}


best[0] = 0;
for (int c = 0; c < 6; c++)
for (int amount = coin[c]; amount < 505; amount++)
best[amount] = min(best[amount], best[amount - coin[c]] + 1);



while (1) {
int total = 0;
for (int i = 0; i < 6; i++) {
scanf("%d", &stock[i]);
total += stock[i];
}
if (!total)
break;
scanf("%d.%d", &dollars, &cents);
int money = dollars * 100 + cents;

printf("%3d\n", getMin(money, 5));
}
return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: