6

私は完全に立ち往生しており、これを解決する方法がわかりません。私が配列を持っているとしましょう

arr = [1, 4, 5, 10]

と数字

n = 8

nに等しいarr内からの最短シーケンスが必要です。たとえば、 arr 内の次のシーケンスは n に等しい

c1 = 5,1,1,1
c2 = 4,4
c3= 1,1,1,1,1,1,1,1

したがって、上記の場合、答えは c2 です。なぜなら、それは arr で sum に等しい最短のシーケンスだからです。

上記の解決策を見つける最も簡単な方法は何ですか？どんなアイデアや助けも本当に感謝しています。

ありがとう！

編集:

  • 配列を修正しました
  • 配列は、正の値のみを持つ可能性があります。
  • おそらく私自身の無知のために、サブセットの問題がこれをどのように修正するかわかりません。サブセットアルゴリズムは常に合計に等しい最短のシーケンスを提供しますか? たとえば、サブセットの問題は、上記のシナリオの答えとして c2 を識別しますか?
4

5 に答える 5

3

将来この質問を見つける人々のために-

Oscar Lopez と Priyank Bhatnagar が指摘したように、これはコインの変更 (変更を与える、変更を行う) 問題です。

一般に、彼らが提案した動的計画法の解決策は、(おそらく!) 常に最小の項目を使用して必要な合計を生成するという点と、実行速度の点で最適な解決策です。基底数が任意の場合は、動的計画法のソリューションを使用してください。

ただし、基底数が「良い」場合は、より単純な貪欲なアルゴリズムで十分です。

たとえば、オーストラリアの通貨システムでは、 の単位が使用されます$100, $50, $20, $10, $5, $2, $1, $0.50, $0.20, $0.10, $0.05。残りの金額がゼロ (または 5 セント未満) になるまで、可能な最大の変更単位を繰り返し与えることによって、任意の金額に対して最適な変更を与えることができます。

これは、貪欲なアルゴリズムの有益な実装であり、概念を示しています。

def greedy_give_change (denominations, amount):        
    # Sort from largest to smallest
    denominations = sorted(denominations, reverse=True)

    # number of each note/coin given
    change_given = list()

    for d in denominations:
        while amount > d:
            change_given.append(d)
            amount -= d

    return change_given

australian_coins = [100, 50, 20, 10, 5, 2, 1, 0.50, 0.20, 0.10, 0.05]
change = greedy_give_change(australian_coins, 313.37)
print (change)           # [100, 100, 100, 10, 2, 1, 0.2, 0.1, 0.05]
print (sum(change))      # 313.35

denominations = [1, 4, 5, 10]元の投稿 (および)の特定の例ではamount = 8、貪欲なソリューションは最適ではありません[5, 1, 1, 1]。しかし、貪欲なソリューションは、動的計画法のソリューションよりもはるかに高速で単純なので、使用できる場合は使用する必要があります。

于 2012-04-01T17:46:06.233 に答える
3

前に指摘したように、これは小銭硬貨の問題であり、通常は動的計画法で解決されます。これは、時間の複雑さ O(nC) と空間の複雑さ O(C) で解決された Python 実装です。ここで、nはコインの数とC必要な金額です。

def min_change(V, C):
    table, solution = min_change_table(V, C)
    num_coins, coins = table[-1], []
    if num_coins == float('inf'):
        return []
    while C > 0:
        coins.append(V[solution[C]])
        C -= V[solution[C]]
    return coins

def min_change_table(V, C):
    m, n = C+1, len(V)
    table, solution = [0] * m, [0] * m
    for i in xrange(1, m):
        minNum, minIdx = float('inf'), -1
        for j in xrange(n):
            if V[j] <= i and 1 + table[i - V[j]] < minNum:
                minNum = 1 + table[i - V[j]]
                minIdx = j
        table[i] = minNum
        solution[i] = minIdx
    return (table, solution)

上記の関数Vには、可能なコインとC必要な金額のリストがあります。関数を呼び出すとmin_change、出力は期待どおりになります。

min_change([1,4,5,10], 8)
> [4, 4]
于 2012-04-01T17:26:54.683 に答える
2

これは、最小コイン変更問題として知られている問題です。

動的計画法を使えば解けます。擬似コードは次のとおりです。

Set MinCoin[i] equal to Infinity for all of i
MinCoin[0] = 0

For i = 1 to N // The number N
For j = 0 to M - 1 // M denominations given
// Number i is broken into i-Value[j] for which we already know the answer
// And we update if it gives us lesser value than previous known.
   If (Value[j] <= i and MinCoin[i-Value[j]]+1 < MinCoin[i])
       MinCoin[i] = MinCoin[i-Value[j]]+1

Output MinCoin[N]
于 2012-04-01T17:06:36.563 に答える
1

これは部分和問題の一種です。あなたの問題では、アイテムを数回選ぶことができます。動的プログラミング手法を使用することで、同様のアイデアを使用してこの問題を解決することができます。基本的な考え方は、関数 F(k, j) を設計することです。F(k, j) = 1 は、和が j で長さが k の arr からのシーケンスがあることを意味します。

正式には、arr[i] = k のような i が存在する場合、基本ケースは F(k, 1) = 1 です。帰納的な場合、arr[i] = m、および F(k-1, jm) = 1 のような i が存在する場合、F(k, j) = 1 です。

F(k, n) = 1 の最小の k は、必要な最短のシーケンスの長さです。

動的計画法を使用すると、再帰を使用せずに関数 F を計算できます。F(k, j) ごとに追加情報を追跡することで、最短シーケンスを再構築することもできます。

于 2012-04-01T13:05:05.817 に答える