any better way to implement this [closed]

Question

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 7 years ago.

Improve this question

i was surfing the internet when i came across this algorithm(making change) and implemented it as below...but still is there any efficient way to do this...also how can i find the complexity for the same from program i implemented...

1>algorithm is as follows

makechange(c[],n) //c will contain the coins which we can take as our soln choice and 'n' is the amount we want change for
soln<-NULL//set that will hold solution
sum=0
while(sum!=n)
{
    x<-largest item in c such that sum+x<=n
    if(there is no such item)
    return not found
    soln <- soln U {a coin of value x}
    sum=sum+x
    return soln
}

2>here is what i have tried

#include<stdio.h>
#include<conio.h>

void main() {
    int c[]= {100,50,20,10,5,1},soln[6];
    int num,i,j,sum=0,x,k,flag=0;
    clrscr();
    printf("\nEnter amount to make change:");
    scanf("%d",&num);

    for(i=0;i<6;i++) {
        soln[i]=NULL;
    }

    j=0;
    while(sum!=num) {
        for(i=0;i<6;i++) {
            if(sum+c[i]<=num) {
                x=c[i];
                break;
            }
        }

        sum=sum+x;
        for(k=0;k<6;k++) {
            if(soln[k]==x) {
                flag=1;
            }
        }

        if(flag!=1)
        soln[j]=x;
        j++;
    }

    printf("\nsoln contains coins below:");
    j=0;

    while(soln[j]!=NULL) {
        printf("%d ",soln[j]);
        j++;
    }
    getch();
}

any help would be appreciated...thank you...

Answer 1

For fun, here's a constexpr version!

template <int... denomination>
    static constexpr auto change(int amount) -> decltype(make_tuple(denomination...))
    {
        typedef decltype(make_tuple(denomination...)) R;
        return R { [&]() { auto fill=amount/denomination; amount-=denomination*fill; return fill;}()... };
    }

Demo: Live On Coliru

#include <boost/tuple/tuple_io.hpp>
#include <iostream>

using boost::tuple;
using boost::make_tuple;

template <int... denomination>
    static constexpr auto change(int amount) -> decltype(make_tuple(denomination...))
    {
        typedef decltype(make_tuple(denomination...)) R;
        return R { [&]() { auto fill=amount/denomination; amount-=denomination*fill; return fill;}()... };
    }

int main() {
    auto coins = change<100,50,20,10,5,1>(367);
    std::cout << coins;
}

Output:

(3 1 0 1 1 2)

Version without boost: http://liveworkspace.org/code/3uU2AS$0

For absolute awesome, this is the disassembly of the non-boost version compiled by clang with -O2. http://paste.ubuntu.com/5632315/

Notice the pattern 3 1 0 1 1 2?

400826:   be 03 00 00 00          mov    $0x3,%esi
...
400847:   be 01 00 00 00          mov    $0x1,%esi
...
400868:   31 f6                   xor    %esi,%esi
...
400886:   be 01 00 00 00          mov    $0x1,%esi
...
4008a7:   be 01 00 00 00          mov    $0x1,%esi
...
4008c8:   be 02 00 00 00          mov    $0x2,%esi

It was completely compiletime evaluated!

Answer 2

The other approach is to go through the coin options, staring with the largest, and taking as many of those as you can without going negative, and then on to the next largest, and so on:

#define RESULT_EXACT   1
#define RESULT_INEXACT 0

int i;
int result_exact = RESULT_EXACT;

for (i=0; i<6; i++) {
    soln[i] = n/c[i]; // How many of this value do we need
    n -= soln[i]*c[i]; // We've now given that amount away
}

if (n!=0) result_exact = RESULT_INEXACT;

Obviously (I hope) this require that c stores the coin values from largest to smallest and requires a check on result_exact to know if the change is exactly correct.