UC知道数学建模 选课问题
来源：百度知道 编辑：UC知道 时间：2024/09/24 22:26:32
某同学考虑下学期的选课，其中必修课只有一门（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限选人数最少。请考虑选课时的先后顺序（先选者先录，人满停选）。
限选课课号 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限选人数最少。请考虑选课时的先后顺序（先选者先录，人满停选）。
这个题在高中的信息学奥林匹克竞赛(OI)中有解决的方法
别的地方相同的问题要求选的课是有顺序的，要先修哪个后修哪个，你这个问题是无序的。
1.你可以参照最小费用最大流算法适当地进行建模。（实在不懂你语言）
2.可能可以使用树型动态规划算法，拓扑建树，转为二叉树，进行树型DP.
3.使用多次背包算法，先把给出的图用拓扑排序算法构建成树，在树里面的每个结点使用背包算法，计算出当前点以下用一定时间能得到的最大学分，多个背包向父亲结点背包。
你粘贴数据的时候把数据弄乱了，是没有办法做的