# Programming Algorithm Prob

• Oct 11th 2006, 10:51 PM
fifthrapiers
Programming Algorithm Prob
QUESTION: Change DPChange to return not only the smallest number of coins, but to also return the correct combination of coins.

DPChange (M, c, d)
1 bestNumCoins_0 <-- 0
2 for m <-- 1 to M
3 *indent*bestNumCoins_m <-- infinity
4 *indent*for i <-- 1 to d
5 *indent**indent*if m >= c_i
6 *indent**indent**indent*if bestNumCoins_(m-c_i) + 1 < bestNumCoins_m
7 *indent**indent**indent**indent*bestNumCoins_M <-- bestNumCoins_(m-c_i) + 1
8 return bestNumCoins_M

NOTE: for line 7, shouldn't be going on a diff line but couldnt fit all in 1...

*EDIT* Nevermind on note, looks like it all fit.

Thanks for any help. I hate programming and it shouldn't be part of math !
• Oct 12th 2006, 12:13 AM
CaptainBlack
Quote:

Originally Posted by fifthrapiers
QUESTION: Change DPChange to return not only the smallest number of coins, but to also return the correct combination of coins.

DPChange (M, c, d)
1 bestNumCoins_0 <-- 0
2 for m <-- 1 to M
3 ............bestNumCoins_m <-- infinity
4 ............for i <-- 1 to d
5 ........................if m >= c_i
6 ...................................if bestNumCoins_(m-c_i) + 1 < bestNumCoins_m
7 ...........................................bestNumCoins_M <-- bestNumCoins_(m-c_i) + 1
8 return bestNumCoins_M

NOTE: for line 7, shouldn't be going on a diff line but couldnt fit all in 1...

*EDIT* Nevermind on note, looks like it all fit.

Thanks for any help. I hate programming and it shouldn't be part of math !

You will not get any constructive help from this starting point.

As it is you are leaving it to the reader to work out what algorithm is
supposed to be implemented by this pseudo-code, as well as what the
parameters are.

To me it looks like this is an attempt at a recursive function to find
the minimum number of coins to make change M from a coin set c[1..d],
but I am guessing. If I am right this is very far from being correct, and so
modification to return the optimal change set as well as the size of that
set is premature.

As a first step you should include comments on what all the parameters
are, what sort of thing bestNumCoins is (array, function ..?) and an
algorithm description in plain language.

Also is this the form of pseudo-code that you have been taught?

RonL
• Oct 12th 2006, 10:11 AM
fifthrapiers
It's a problem copied right from a book "An Introduction to Bioinformatics Algorithms" by Neil Jones and Pavel Pevzner. Yes, this is the 'pseudocode' we have been using.

The only additional information it gives is:

"The algorithm with running time O(Md) calculates bestNumCoins_m for increasing values of m. This works because the best number of coins for some value m depends only on values less than m." "The DPChange algorithm provides a simple O(Md) solution...Conversely, a minor modification of the Change problem renders the problem very difficult."

Now I have to correct it to return correct combination of coins.
• Oct 12th 2006, 12:38 PM
CaptainBlack
Quote:

Originally Posted by fifthrapiers
It's a problem copied right from a book "An Introduction to Bioinformatics Algorithms" by Neil Jones and Pavel Pevzner. Yes, this is the 'pseudocode' we have been using.

The only additional information it gives is:

"The algorithm with running time O(Md) calculates bestNumCoins_m for increasing values of m. This works because the best number of coins for some value m depends only on values less than m." "The DPChange algorithm provides a simple O(Md) solution...Conversely, a minor modification of the Change problem renders the problem very difficult."

Now I have to correct it to return correct combination of coins.

You will find this easier to do with the correct pseudo-code:

DPChange (M, c, d)
//
// Arguments
// ========
// M the amount of change to be made
// c and array containing the coin denominations (in no particular order)
// d the number of denominations (ie the number of elements of c)
//
// Local Variables
// ===========
//
// bestNumCoins[0..M] array containing the optimal number of coins
// ....bestNumCoins(m) to make make change m. At end of processing
// ....bestNumCoin(M) will contain the minimum number of coins to
// ....make change for M
// i index for loop over the coin denominations
// m index for loop over amounts to make change for from 0 to M
//
1 bestNumCoins_0 <-- 0
2 for m <-- 1 to M
3 ............bestNumCoins_m <-- infinity
4 ............for i <-- 1 to d
//
// this next section computes min( bestNumCoins(m), bestNumCoins(m-c(i)) + 1 )
//
5 ........................if m >= c_i
6 ...................................if bestNumCoins_(m-c_i) + 1 < bestNumCoins_m
7 ...........................................bestNumCoins_m <-- bestNumCoins_(m-c_i) + 1
//
// end of the section
//
8 return bestNumCoins_M

I don't think that you realise how much work is involved in correcting this

RonL
• Oct 12th 2006, 01:13 PM
CaptainBlack
Quote:

Originally Posted by CaptainBlack
You will find this easier to do with the correct pseudo-code:

DPChange (M, c, d)
//
// Arguments
// ========
// M the amount of change to be made
// c and array containing the coin denominations (in no particular order)
// d the number of denominations (ie the number of elements of c)
//
// Local Variables
// ===========
//
// bestNumCoins[0..M] array containing the optimal number of coins
// ....bestNumCoins(m) to make make change m. At end of processing
// ....bestNumCoin(M) will contain the minimum number of coins to
// ....make change for M
// i index for loop over the coin denominations
// m index for loop over amounts to make change for from 0 to M
//
1 bestNumCoins_0 <-- 0
2 for m <-- 1 to M
3 ............bestNumCoins_m <-- infinity
4 ............for i <-- 1 to d
//
// this next section computes min( bestNumCoins(m), bestNumCoins(m-c(i)) + 1 )
//
5 ........................if m >= c_i
6 ...................................if bestNumCoins_(m-c_i) + 1 < bestNumCoins_m
7 ...........................................bestNumCoins_m <-- bestNumCoins_(m-c_i) + 1
//
// end of the section
//
8 return bestNumCoins_M

I don't think that you realise how much work is involved in correcting this

RonL

Now that we have corrected code we can think about solving the problem as
set. We need to introduce a 2D array bestComb(0..M)(1..d) which for each
change amount 0 .. M, contains the numbers of each denomination c(1) to
c(d). This is initialsied to zeros, and as we compute bestNumCoins(m) we
also compute bestComb(m).

DPChange (M, c, d)
//
// Arguments
// ========
// M the amount of change to be made
// c and array containing the coin denominations (in no particular order)
// d the number of denominations (ie the number of elements of c)
//
// Local Variables
// ===========
//
// bestNumCoins[0..M] array containing the optimal number of coins
// ....bestNumCoins(m) to make make change m. At end of processing
// ....bestNumCoin(M) will contain the minimum number of coins to
// ....make change for M
// bestComb[0..M][1..d] 2d array containing the coin counts for the
//.....best combination bestComb[a][b] is the number of coins of the b-th
//.....denomination in the best change combination for amount a.
// i index for loop over the coin denominations
// m index for loop over amounts to make change for from 0 to M
//
1 bestNumCoins[0] <-- 0
2 bestComb<--zeros(M+1,d)
3 for m <-- 1 to M
4............bestNumCoins[m] <-- infinity
5............for i <-- 1 to d
//
// this next section computes min( bestNumCoins[m], bestNumCoins[m-c[i]] + 1 )
// and also sets the best combination so far
//
6........................if m >= c[i]
7...................................if bestNumCoins[m-c[i]] + 1 < bestNumCoins[m]
8...........................................bestNumCoins[m] <-- bestNumCoins[m-c[i]] + 1
9...........................................bestComb[m]<--bestComb[m-c[i]]
10..........................................bestComb[m][i]<--bestComb[m-c[i]][i]+1
//
// end of the section
//
11 return bestNumCoins[M], bestComb[M]

Without a system that will run the pseudo-code I won't guarantee its
correctness.

RonL

(By the way if those authors worked for me and turned their algorithm in as a
piece of work with no further explanation, they would be seeing no salary review
this year, and be cleaning the bogs for a month)
• Oct 12th 2006, 03:15 PM
fifthrapiers
Indeed, my professor said it would be very complicated, and she didn't intend it to be this complicated but after she did it she realized it was. Wow, I didn't think it would be THAT complicated. Ugh! I am going to look through it now. I really appreciate you going through it. Thanks CaptainBlack.
• Oct 12th 2006, 03:34 PM
fifthrapiers
In case you were curious, the way my professor did it was by creating a 2-dimensional array, say a, so that a(sub-i, sub-j) is the number of coins of type j that are used in making change for i cents.
• Oct 12th 2006, 04:23 PM
CaptainBlack
Quote:

Originally Posted by fifthrapiers
In case you were curious, the way my professor did it was by creating a 2-dimensional array, say a, so that a(sub-i, sub-j) is the number of coins of type j that are used in making change for i cents.

Which is what my bestComb array is:cool:

RonL