動的計画法で

質問

「２、３、７のいずれかの数字が書かれているカードがそれぞれ何枚かある。
それらを各１枚以上組み合わせて、書かれている数字の合計を２５にするにはどのようにすればいいか」
という問題を考えるときに、普通に考えれば、
１枚ずつ使うのだから２５－(２＋３＋７)＝１３を作ることを考え、あと７のカードを１枚、３を２枚追加し、「７を２枚、３を３枚、２を１枚、合計６枚」という答えが得られそうですが、これを動的計画法で(正しく)考えるとするとどんな考え方になるのでしょうか。

つまり、１枚ずつ組み合わせた１２を別に考えるのは是か非か、また残りの１３を「６は３が２枚が最適、７は７が１枚が最適、だから足した１３は６の場合と７の場合を足したものが最適」というように明記しないといけないかという質問です。

回答No.2

Tacosan · ベストアンサー

まず, 「2, 3, 7 のいずれかが書かれたカードがあり, どの種類のカードも 1枚以上使って合計で 25にする」ということですから, 全て 1枚ずつ使った 12 からスタートして何枚かカードを追加することにより 25 を作ることになります. つまり, 「2, 3, 7 のいずれかが書かれたカードがあり, 何枚かのカードを使って合計で 25 - 12 = 13 を作る」という問題になります.

さて, ここで「この 3種類のカードで作ることのできる数値」を次のように組織的に見付けることにしましょう.
【準備するもの】0, 1, 2, ... と番号の付いた表 1個, こま 1個.

まず, 「0」を作ることはできます (どのカードも使わない, ということですね). そこで, 表の「0」の欄にチェックして, こまを「0」の欄に置きます. これは, 「今は 『0』に着目する」という意味です.

今「0」ができているわけですから, カードを 1枚追加することにより「2」, 「3」, 「7」を作ることができます. これらの欄にチェックをしましょう. 「0」にカードを 1枚追加してできるのはこの 3種類だけですので, 「0」の次に小さい, チェックが入っている数値を見付けましょう. 「2」ですので「2」の欄にこまを動かします.

今度は「2」にカードを 1枚追加すると何ができるかを考えます. ここでは「4」, 「5」, 「9」を作ることができます. これらの欄に, やはりチェックしましょう. これで「2」も終わったので, 次に小さい「3」の欄にこまを動かします.

以下, 必要なところまで順に調べていきます.

このように「既に見付かった数値に, さらにカードを 1枚追加することによりどのような値になるか」を表に基づいて小さい方から順に調べていくのが (この問題での) 動的計画法です.

この説明では, ある値が作れるか作れないかだけしかわかりませんが, チェックする代わりに使った枚数を記録していくことにより最小 (あるいは最大) で何枚のカードを使うか, ということまで調べることができます.

最後に「使った枚数がわかったとして, ではどのカードを使えばよいのか」という点もおさえておきましょう.

今の例では「13」が 3枚でできることがわかります. ということは, 「13 - 2 = 11」, 「13 - 3 = 10」, 「13 - 7 = 6」のどれかが 2枚でできることになります. 「10」を選んだとすれば, これはつまり「『10』を 2枚でつくり, そこに『3』を 1枚追加する」ことを意味します. さらに「10」が 2枚でできることもわかりますので, 「10 - 2 = 8」, 「10 - 3 = 7」, 「10 - 7 = 3」のいずれかが 1枚でできるということになります. このように, 枚数を考えながら「どのカードを使えばいいのか」を逆に調べることにより「どのカードを使えばいいのか」がわかります.

お礼

詳しい解説をしていただきありがとうございました。
大変よくわかりました。

回答No.1

neKo_deux

> １枚ずつ組み合わせた１２を別に考えるのは是か非か、

元の問題から「それらを各１枚以上組み合わせて、」の条件が余分であるならＯＫです。

「２、３、７のいずれかの数字が書かれているカードがそれぞれ何枚かある。
それらを組み合わせて、書かれている数字の合計を１３にするにはどのようにすればいいか」

と置き換えできますね。

> また残りの１３を
> 最適

何が最適かは設問されていないのでは？
７を１枚、３を２枚、２を６枚で、合計９枚と枚数が多いのが最適かも知れないし…

--
> これを動的計画法で(正しく)考えるとするとどんな考え方になるのでしょうか。

２、３、７のカードの枚数をx1, x2, x3とします。
1≦x1, 1≦x2, 1≦x3
2*x1 + 3*x2 + 7*x3 = 25
という条件を、
x1=1, x2=1, x3=1の時満たすかどうか？
x1=2, x2=1, x3=1の時満たすかどうか？
x1=3, x2=1, x3=1の時満たすかどうか？
・
・
x1はどこまで計算して止めればよいか？

…などと逐次計算していく手順だったと思います。
「動的計画法 ナップザック問題」で情報収集すると良いかも。

お礼

この問題での「最適」とは使う枚数が少ないという意味のようです。

質問のままだと単なる欲張り法の真似事な気がして、部分解が最適だから全体も最適だという方針ではない気がしていました。