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

デモ：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;
}

出力：

(3 1 0 1 1 2)

ブーストなしのバージョン：http：//liveworkspace.org/code/3uU2AS$0

絶対に素晴らしいのは、これは-O2を使用してclangによってコンパイルされ た非ブーストバージョンの逆アセンブルです。http://paste.ubuntu.com/5632315/

パターン310 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

もう 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 に答える