-1

当我遇到这个算法（进行更改）并将其实现如下时，我正在网上冲浪......但仍然有任何有效的方法可以做到这一点......我如何从我实现的程序中找到相同的复杂性...

1>算法如下

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

任何帮助将不胜感激...谢谢...

4

2 回答 2

14

为了好玩，这里有一个constexpr版本！

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;}()... };
    }

演示：在 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;
}

输出：

(3 1 0 1 1 2)

没有提升的版本：http: //liveworkspace.org/code/3uU2AS$0

对于绝对真棒，这是由clang用-O2编译 的非boost版本的反汇编。http://paste.ubuntu.com/5632315/

注意到模式 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

它完全是编译时评估的！

于 2013-03-20T20:27:53.853 回答
1

另一种方法是通过硬币选项，盯着最大的，尽可能多地选择而不是负数，然后选择下一个最大的，依此类推：

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

显然（我希望）这需要c从最大到最小存储硬币值，并且需要检查result_exact以了解更改是否完全正确。

于 2013-03-20T19:27:50.193 回答