一、指派问题
分析:此题需要使用匈牙利算法,匈牙利算法是一种组合优化算法,通过不断的寻找增广路径来实现对于任务的最大覆盖,对于此题解题思路如下:
1)寻找每行的最小值,并且每个值于此值做差,形成下表:
1 | 2 | 3 | 4 | |
甲 | 0 | 13 | 11 | 2 |
乙 | 6 | 0 | 10 | 11 |
丙 | 0 | 5 | 7 | 4 |
丁 | 0 | 1 | 4 | 2 |
2)寻找每列的最小值,并且每个值与此值做差,形成下表:
1 | 2 | 3 | 4 | |
甲 | 0 | 13 | 7 | 0 |
乙 | 6 | 0 | 6 | 9 |
丙 | 0 | 5 | 3 | 2 |
丁 | 0 | 1 | 0 | 0 |
通过上表的执行结果,可以看到,甲可以做1和4,乙只能做2,丙只能做1,所以甲做4,乙做2,丙做1,丁做3,此题答案为C
二、最值问题
分析:此种问题只能使用穷举法,穷举所有的情况,取最大值。
上图中,如果400万都给丙,最大获利 1500万元,穷举下列场景:
1)200+200: 最大获利:8+9=17
2)300+100:最大获利:11+4=15
3)200+100+100:最大获利:9+4+5=18
所以答案为B
三、资源分配问题:
分析:
首先计算每个箱号单位重量的利润,如下表所示:
箱号 | 1 | 2 | 3 | 4 | 5 | 6 |
重量 | 8 | 13 | 6 | 9 | 5 | 7 |
利润 | 3 | 5 | 2 | 4 | 2 | 3 |
单位利润 | 0.375 | 0.384 | 0.333 | 0.444 | 0.4 | 0.428 |
所以要优先选择4,6,这样重量为9+7=16还剩余 24-16=8吨,只能选择1,所以选择,1,4,6
其利润为:3+4+3=10 答案为B