数学建模选课问题,求大神解答

问题描述：

数学建模选课问题,求大神解答

试问：

1）为了达到学校和院系的规定,该同学下学期最少应该选几门课?应该选哪几门课?

2）若考虑在选修最少学分的情况下,该同学最多可以选修几门课?选哪几门?

选做：

3）若考虑到选修时课程能否如愿选上的问题,请多准备几套选择方案.已知课程限选人数为1,2,3,4限选人数最多,5,6,7,8次之,13、17、18限选人数最少.请考虑选课时的先后顺序（先选者先录,人满停选）.

1个回答分类：数学 2014-09-28

问题解答：

我来补答

这个问题应该算是一个0-1背包问题吧.18个学分算是背包容量,每门课的学分是物体体积,物品收益都相同,是1.
第一问属于背包的最少收益问题,第二问是最大收益问题.
然后这个问题应该就可以用经典背包问题求解算法了.比如动态规划：
对课程1,考虑选择它和不选择它
如果选择它,就只需要再选择13个学分,然后这个问题会简化为要选择13个学分,少了课程1后的课程选择问题,问题还是原先的问题,但是问题的规模小了点,剩下的继续递归.
如果不选择它,就需要选择18个学分,问题简化为18个学分,但是没有课程1,剩下的也递归下去.
两种选择,哪种优选择哪一个.

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

展开全文阅读