Question

数学建模选课问题完整解答

选课问题
某同学考虑下学期的选课，其中必修课只有一门（2学分），可供选修的限定选修课（限选课）有8门，任意选修课（任选课）有10门。由于有些课程之间相互关联，所以可能在选修某门课程时必须同时选修其他某门课程，课程信息见下表：
限选课课号 1 2 3 4 5 6 7 8
学分 5 5 4 4 3 3 3 2
同时选修要求 1 2
任选课课号 9 10 11 12 13 14 15 16 17 18
学分 3 3 3 2 2 2 1 1 1 1
同时选修要求 8 6 4 5 7 6
按学校规定，学生每个学期选修的总学分数不能少于20学分，因此该同学必须在上述18门课中至少选修18个学分，学校还规定学生每学期选修任选课的比例不能少于所修总学分（包括2个必修学分）的1/6,也不能超过所修总学分的1/3。学院也规定，课号为5，6，7，8的课程必须至少选一门。

试问：
1）为了达到学校和院系的规定，该同学下学期最少应该选几门课？应该选哪几门课？
2）若考虑在选修最少学分的情况下，该同学最多可以选修几门课？选哪几门？
3）若考虑到选修时课程能否如愿选上的问题，请多准备几套选择方案。已知课程限选人数为1，2，3，4限选人数最多，5，6，7，8次之，13、17、18限选人数最少。请考虑选课时的先后顺序（先选者先录，人满停选）。
急求完整解答！！！！！！！！！！！求大吓帮助啊！！

Answer 1

这个问题应该算是一个0-1背包问题吧。18个学分算是背包容量，每门课的学分是物体体积，物品收益都相同，是1.

第一问属于背包的最少收益问题，第二问是最大收益问题。

然后这个问题应该就可以用经典背包问题求解算法了。比如动态规划：
对课程1，考虑选择它和不选择它
如果选择它，就只需要再选择13个学分，然后这个问题会简化为要选择13个学分，少了课程1后的课程选择问题，问题还是原先的问题，但是问题的规模小了点，剩下的继续递归。
如果不选择它，就需要选择18个学分，，问题简化为18个学分，但是没有课程1，剩下的也递归下去。
两种选择，哪种优选择哪一个。

当进行递归的时候，如果碰到选择方案不能满足约束条件，即任选课大约1/6小于1/3，则该方案返回0值，如果还有同修要求的，比如限选课6，如果开始选择的是不选课程1，那么对于课程6，就不存在选择和不选择问题了，必然是不选择，如果开始第一步选择了课程1，当递归到课程6的时候才有选择和不选两种选择。

最终会得到一组第一问和第二问的最优解，则第三问结果也有了。

另外，附赠一个思路：可以查一下关键词【演化算法】，不用确定性算法，而是用智能优化算法，将所有的课用一个二进制位进行编码，0表示不选，1表示选择。每一种01串表示一种课程选择策略，对应一个学分，还对应一个对各种约束的满足程度，将对约束的违反当做罚函数。然后进行演化算法的选择交叉变异就开始搞，反正演化算法不能说来话长，如果感兴趣自己看看。