2

したがって、これはコインに関する 2 つの部分の問題です。最初の部分では、1 ～ 99 セントのコイン カウントを合計します (たとえば、1 セントになるには 1 コイン、2 セントになるには 2 コイン、など)。各値）。これは、次のコードで表すことができます (提案/改善を自由に行ってください)。

def findbest(origarray, denom):
    current = origarray
    i = 1
    while(i < size):
        if(i in denom):
            current[i] = 1
            coinlist[i] = [i]
        else:
            k = 1
            while(k < 1 + (i/2)):
                c = current[k] + current[i-k]
                if(c < current[i]):
                    current[i] = c
                    coinlist[i] = coinlist[k] + coinlist[i-k]
                k+=1
        print i, current[i], coinlist[i]
        i+=1
    return current


size = 100
coinlist = [[]]
origarray = [0] 
i = 1

while(i < size):
    origarray.append(100)
    coinlist.append([])
    i += 1

denom = [1,5,10,25,50]

x = findbest(origarray, denom)

total=0

for value in findbest(origarray,denom):
    total += value

print total


print "\n\n\n"
print x

問題の 2 番目の部分は、すべてのコイン数の合計が最小になる理想的な 3 つの金種 (実際の金種である必要はありませんが、1 つが 1 である必要があります) を見つけることです。ここが私にとって難しいところです。最適な 3 つ ([1,12,19] であることはわかっていますが、その点に到達することはできません) が見つかるまで、金種の値をブルート フォースする何かを作成する必要があることはわかっていますが、そうではありません。それを行う方法を確認してください。これを行う方法を知っている人はいますか？

4

2 に答える 2

1

あなたが探している関数は、これを完全に簡単にするものですitertools.combinations.

>>> from itertools import combinations
>>> len(list(a for a in combinations(range(1, 101), 3)))
161700

次のようなものに基づいた実装をお勧めします。

def findbest(origarray, denom):
    current = origarray
    i = 1
    while(i < size):
        if(i in denom):
            current[i] = 1
            coinlist[i] = [i]
        else:
            k = 1
            while(k < 1 + (i/2)):
                c = current[k] + current[i-k]
                if(c < current[i]):
                    current[i] = c
                    coinlist[i] = coinlist[k] + coinlist[i-k]
                k+=1
        #print i, current[i], coinlist[i]
        i+=1
    return current

size = 100

def reset_cache():
  i = 1
  global coinlist
  coinlist = [[]]
  global origarray
  origarray = [0] 

  while(i < size):
      origarray.append(100)
      coinlist.append([])
      i += 1

reset_cache()

denom = [1,5,10,25,50]

x = findbest(origarray, denom)

total=0

for value in findbest(origarray,denom):
    total += value

print total


print "\n\n\n"
print x


from itertools import combinations

best = ((0,0,0), 1e6)
for comb in combinations(range(1, 101), 3):
  #print "Considering: %s" % comb
  reset_cache()
  total = 0
  for value in findbest(origarray, comb):
    total += value
  if total < best[1]:
    print "%s beat best with %d" % (comb, total)
    best = (comb, total)

print best

しかし、コインキャッシュと思われるものを必要とすることに悩まされていますか? よくわかりませんが、あなたのコードをよく読んでいませんでした。しかし、それを機能させるためにいくつかの配列を渡す必要があるのは好きではありません。自己完結型である必要があります。

編集：あなたは実際に逃げることができるように私には思えます

for comb in [(1,) + a for a in combinations(range(2, 101), 2)]:

有効な両替システムには 1 セント硬貨が必要だからです。これにより、コードの実行がはるかに高速になります。

>>> len([(1,) + a for a in combinations(range(2, 101), 2)])
4851
于 2013-10-28T02:13:34.457 に答える
1

私のJavaバージョン

public static int minChange(int[] coins, int total) {
        int[] counts = new int[total + 1];
        counts[0] = 0;
        int MAX = Integer.MAX_VALUE - 1;
        for (int i = 1; i <= total; ++i) {
            int count = MAX;
            for (int j = 0; j < coins.length; ++j) {
                if (i - coins[j] >= 0 && count > counts[i - coins[j]])
                    count = counts[i - coins[j]];
            }
            if (count < MAX)
                counts[i] = count + 1;
            else
                counts[i] = MAX;
        }
        return counts[total];
    }
于 2014-10-01T20:56:16.733 に答える