問題は：
数学の 3 クラス、PC プログラミングの 3 クラス、物理学の 2 クラスを 1 週間に 5 日間で混合する可能性をすべて出力します。学生は 1 週間のうち少なくとも 1 クラス、最大で 3 クラスを持っています。どんなに混ざっても」
M: [数学,数学,数学]
T: [PC プログラム,PC プログラム]
W: [PC プログラム]
T: [物理]
F: [物理]
私は Python で 15/5 = 3 (学生が持つことができる最大クラス) のすべてのクラスを含む 15 要素のリストを作成するというアイデアを持っているので、上記の例ではリストは次のようになりますが[m,m,m,cs,cs,0,cs,0,0,p,0,0,p,0,0]、私はそうしません。バックトラッキングを使用してすべてのリストを生成する方法を本当に知りません。アイデアを教えてください。
まず、より簡単な問題を解いてみてください。すべての可能性を出力して、さらに 2 つの制約を持つクラスを混合してみてください。
どのクラスも 1 日に複数回表示することはできません
1日の授業の順番は問いません
バックトラック問題ではいつものように、再帰で解決するのが最も簡単です。次のことを行います: cs、cs、cs、m、m、m、p、p の順序で一連のクラスを取得し、再帰の各ステップで次のクラスを「可能な」日に割り当てます。これまでに割り当てられたクラスが 3 つ未満で、同じタイプのクラスがまだない場合、1 日が可能です。
可能性の繰り返しを避けるために、もう 1 つの要件を追加します。再帰の現在のステップで、クラス A をある日に割り当てる必要があり、クラス A がすでにいくつかの日に追加されている場合は、A を数日後に割り当てるようにしてください。割り当てられた最後の週。これは少し紛らわしいかもしれませんので、例を挙げましょう。
現在の状態があるとします。
M: m, cs
T: 0
W: cs
T: p
F: p
次のステップでは、cs クラスを追加する必要があります。上で説明したように、木曜日と金曜日から数日後だけを試します。いくつかの考慮が必要ですが、この制限を追加しないと、いくつかの可能性が何度も見つかることを理解できるはずです.
再帰の終わりは、次の 2 つのケースで満たされます。
すべてのクラスがある日に割り当てられている場合、可能な割り当てが見つかり、それを出力します
次のステップでクラス A をある日に割り当てる必要があるが、A がすでにある曜日に割り当てられており、X より後のすべての日に 3 つのクラスが割り当てられている場合、可能な日を見つけることができません。 A の場合、この分岐では解決策を見つけることができません。
この少し簡単な問題を解決したので、追加した 2 つの制約を 1 つずつ削除してみてください。最初に、クラスが 1 日に複数回出現するようにソリューションを変更します (ただし、この場合、いくつかの可能性を複数回カウントすることを避けるために、追加の作業が必要になるため、問題はより単純に見えます)。この後、最後に残った制約を取り除きます - 1 日の問題のクラスの順序を作ります。それには簡単なアプローチがありますが、あなたが問題を述べているようにそれが許可されているかどうかはわかりません.
この回答がお役に立てば幸いです。上で述べたすべての問題の解決策を書き留めることができますが、実際に自分でできるように、自分でそれらにアプローチする方法のヒントを提供したいと思います.