# [SQL] Coin Changing problem

Discussion in 'Programming' started by dsound, Sep 12, 2006.

1. ### dsoundNew Member

Joined:
Sep 12, 2006
Messages:
1
Likes Received:
0
Trophy Points:
0
I have an urgent question:

I have a current code that checks for available denominations.
Eg. I have available: 1,000 N - 8
500 N - 1
200 N - 4
Amount: 8,600

The current algorithm loops through:
denom_qty = Amount / (avail_denom where count > 0)
remainder = denom_qty - trunc(denom_qty)
new_amt = avail_denom * remainder

In above: denom_qty = 8600 / 1000 = 8.6
remainder = 8.6 - 8 = 0.6
new_amt = 1000 * 0.6 = 600

When it loops back, it will see that there will be available 500 so:
denom_qty = 600 / 500 = 1.2
remainder = 1.2 - 1 = 0.2
new_amt = 500 * 0.2 = 100

But when it loops back, it will not see any 100 denomination so it will get an error.
But supposedly, the denomination should be ok since the 8,600 amount can be cut by:
8 - 1,000 N and 3 - 200 N.

I have tried this code to remove the non-multiples (denominations that have remainders when divided with the amount):

where c_denom is the list of available denominations, as above:
AMOUNT = 8,600
Available denominations:
1,000 N - 8
500 N - 1
200 N - 8

/*******************
for i in c_denom loop

v_denom_qty := v_new_amt / i.denomination;
v_denom_val := trunc(v_denom_qty,0);
v_remainder := v_denom_qty - v_denom_val;
v_qty1 := nvl(i.ccy_count,0);

if (nvl(v_remainder,0) = 0) OR (v_count = 1) then
if v_qty1 >= v_denom_val then
v_new_amt := v_new_amt - (i.denomination * v_denom_val);
elsif v_qty1 < v_denom_val then
v_new_amt := v_new_amt - (i.denomination * v_qty1);
end if;

v_count := nvl(v_count, 0) + 1;
end if;
end loop;
*********************************/

This code would work for the above scenario, but it won't work for USD currency, with the following:
AMOUNT = 267.56
Available denominations:
100 N - 4 1 C - 1
50 N - 9 0.50 C - 2
20 N - 10 0.25 C - 3
5 N - 2 0.10 C - 4
1 N - 2 0.01 C - 2

Note: 0.56 can be split by 0.25 - 1, 0.10 - 3, and 0.01 - 1

The objective is to check whether my denominations are enough to cover the amount needed. There is actually no need to identify the most optimal combination, although that can be an added feature.

Please help. This is really urgent.