選課演算法

⑴ 數學建模選課問題完整解答

這個問題應該算是一個0-1背包問題吧。18個學分算是背包容量，每門課的學分是物體體積，物品收益都相同，是1.

第一問屬於背包的最少收益問題，第二問是最大收益問題。

然後這個問題應該就可以用經典背包問題求解演算法了。比如動態規劃：
對課程1，考慮選擇它和不選擇它
如果選擇它，就只需要再選擇13個學分，然後這個問題會簡化為要選擇13個學分，少了課程1後的課程選擇問題，問題還是原先的問題，但是問題的規模小了點，剩下的繼續遞歸。
如果不選擇它，就需要選擇18個學分，，問題簡化為18個學分，但是沒有課程1，剩下的也遞歸下去。
兩種選擇，哪種優選擇哪一個。

當進行遞歸的時候，如果碰到選擇方案不能滿足約束條件，即任選課大約1/6小於1/3，則該方案返回0值，如果還有同修要求的，比如限選課6，如果開始選擇的是不選課程1，那麼對於課程6，就不存在選擇和不選擇問題了，必然是不選擇，如果開始第一步選擇了課程1，當遞歸到課程6的時候才有選擇和不選兩種選擇。

最終會得到一組第一問和第二問的最優解，則第三問結果也有了。

另外，附贈一個思路：可以查一下關鍵詞【演化演算法】，不用確定性演算法，而是用智能優化演算法，將所有的課用一個二進制位進行編碼，0表示不選，1表示選擇。每一種01串表示一種課程選擇策略，對應一個學分，還對應一個對各種約束的滿足程度，將對約束的違反當做罰函數。然後進行演化演算法的選擇交叉變異就開始搞，反正演化演算法不能說來話長，如果感興趣自己看看。