6

{1,3,5} 単位の硬貨; 合計 = 11. 合計を作成するために使用できるコインの最小数を見つけます (各金種の任意の数のコインを使用できます)

特に動的計画法を使用して、このコイン変更問題の実行時間の複雑さを検索しました。しかし、どこにも説明を見つけることができませんでした。

非動的ソリューションの複雑さを計算し、それを動的ソリューションに変更するにはどうすればよいですか? (貪欲な方ではありません)

編集：

これは、分析が求められた実装です。

public int findCoinChange(int[] coins, int sum,int count) {

    int ret = 0, maxRet = -1;
    if(sum ==0)maxRet = count;
    else if(sum < 0)maxRet = -1;
    else{
        for(int i:coins){
            ret = findCoinChange(coins, sum - i,count+1);
            if(maxRet< 0)maxRet = ret;
            else if(ret >=0 && ret < maxRet){
                    maxRet = ret;
                }
            }
    }
    if(maxRet < 0)return -1;
    else return maxRet;
}

私にはコンビナトリアル爆発のように見えます。ただし、これの実行時の複雑さを推測する方法がわかりません。

4

1 に答える 1

1

この問題に対する動的プログラミングの解決策は、明らかに O(k * n)(ネストされたループ、何とか何とか) でkあり、 はコインの数であり、nは変更が行われている金額です。

非動的プログラミング ソリューションの意味がわかりません。申し訳ありませんが、意味するアルゴリズムを指定する必要があります。貪欲なアルゴリズムは場合によっては失敗するため、それについて言及するべきではありません。線形計画法ソリューションのことですか? 複雑さが何であるかがわからないため、これはこの問題に対するひどいアプローチであり、任意にゆっくりと実行することが可能です。

また、「動的なものに変更する」という意味もわかりません。

于 2013-06-21T03:52:43.333 に答える