1

この問題を説明する方法を理解するのに苦労しています。私は現在、プログラミングのクラスで追加の単位を取得するためにプログラムを作成しようとしていますが、その背後にある数学さえ理解していません....だから、誰かが私を助けてくれるとうれしいです. 大丈夫：

1セント硬貨と4セント硬貨があるとします。許可されるコインの総数は 4 です。値の最大範囲は 11 です。チャートは以下のとおりです。

Value | 1 cent | 4 cent
 1    | 1
 2    | 2
 3    | 3
 4    | 4
 5    | 1      | 1
 6    | 2      | 1
 7    | 3      | 1
 8    |        | 2
 9    | 1      | 2
10    | 2      | 2
11    | Maximum

S0 それは例です。私はこれをはるかに大きな数にする必要があります。しかし、誰かが私のために数学を説明するのを手伝ってくれると嬉しいです. または、方程式は何ですか... それは私を狂気に駆り立てています。

ナップザック アルゴリズムのバージョンを実装しようとしましたが、うまくいかないようです。誰かが助けることができれば、それは大歓迎です。それができるかどうか、またはこのソリューションに貪欲なアルゴリズムを使用する必要があるかどうかはわかりません。これは基本的に貪欲なアルゴリズムのひねりです。

編集：11に変更

4

2 に答える 2

2

この問題を解決する方法が動的計画法 (DP) です。DP では一般に、そのプロパティの他の値に基づいて計算できるいくつかの基本的なプロパティを見つける必要があります。帰納的推論の形式です。

あなたの場合、尋ねる必要がある基本的な質問は次のとおりです。これは単純なブール値の yes/no です。コインは再利用できるので、コインでセントを作る方法を知る必要はありません。それが可能かどうかだけです。これは、指定された種類のコインでセントを作ることができる場合、ブール値の行列を暗黙的に定義します。nkA[n][k]A[n][k] = TRUEnk

この真理値表のさまざまなエントリ間の関係を調べてください。たとえば、2 枚のコインで 5 セントを稼ぐことができる場合、3 枚のコインでそれぞれ 6 セントと 9 セントを稼ぐことができます (なぜですか?)。したがって、 と をA[5][2]意味A[6][3]しA[9][3]ます。

幸運を！

于 2013-03-12T02:00:46.203 に答える