1

事務用品店では、お気に入りの種類のペンを 5 本、8 本、または 24 本入りのパッケージで販売しています。したがって、たとえば、正確に 13 本のペンを購入することは可能ですが (1 つのパッケージには 5 本入り、もう 1 つのパッケージには 8 本入り)、正確に 11 本のペンを購入することはできません。正確に n 本のペンを購入できるかどうかを判断するには、次のような a、b、c の非負の整数値を見つける必要があります。

5a + 8b + 24c = n

1 つの引数 n を取り、ペンの総数が正確に n に等しくなるように 5、8、および 24 パック単位の組み合わせを購入できる場合は True を返し、それ以外の場合は False を返す numPens という関数を作成します。

注: 先月の中間試験で出題された問題です。私はそれを解決できませんでしたが、まだ解決策を探しています。どんな助けも受け入れられます。Python のコードまたはそれを解決するためのアルゴリズム。ありがとう

4

1 に答える 1

3

これは、動的計画法の良い候補のように思えます。

def numPens(n):
  pen_sizes = [5, 8, 24]
  results = [True]
  for i in range(1, n+1):
    results.append(any(i >= size and results[i - size] for size in pen_sizes))
  return results[n]

ここでの重要な洞察は次のとおりです。

  1. 0 ペンを達成できます (自明: 各サイズの 0 パック)。
  2. n 本未満のペンの答えがわかっている場合、n 本のペンを取得できるかどうかを計算できます。

たとえば、0 から 9 までの答えが既にわかっていると仮定して、10 本のペンを入手できるかどうかを知りたいとします。そうするには、少なくとも 1 つのパックが必要です。次に、考慮すべき 3 つのケースがあります。

  1. 5本入りパック + ただし、ペンが5本入手可能な場合は、5本のペンを入手できます。
  2. 8本入りパック + ただし、2本のペンを入手できる場合は、2本のペンを入手できます。
  3. 24 本入りパック + ただし、-14 ペンを入手できる場合は、-14 ペンを入手します。

これらの最後のものは無意味なので、5 本のペンを入手できるか 2 本のペンを入手できる場合に限り、10 本のペンを入手できます。0 から 9 までの答えが既にわかっていると仮定しているので、問題を解くことができます (5 本のパックとして 5 本のペンが可能であることが判明したため、10 個も同様であると結論付けます)。

したがって、n の小さい値に対する答えが常にある状況に身を置くために、0 に対する明らかな答えから始めます。次に、1 に対する答えを計算します (0 に対する答えは既にあるので、次のことができます)。これを行う）。次に、2 の答えを計算します (既に 0 と 1 があるので、これを行うことができます)、というように、必要な n の答えが得られるまで続けます。

このコードのビットは、前の結果からの結果の実際の計算をカプセル化します:そのサイズのパックを購入するのが理にかなっているTrueパックサイズがある場合に生成します ( の負の数を取得することなく)。ペンを購入する方法。sizei - sizei - size

any(i >= size and results[i - size] for size in pen_sizes)

コードの残りの部分では、results将来の使用のためにその結果をリストに保存し、最終的に最終結果を返すだけです。

于 2013-04-21T19:31:50.377 に答える