平成29年度秋期 ITパスポート試験問1

这道题的解析和你的作答记录。

問1

頻出度★★★

表は，技術者A，B，C がそれぞれ製品X，Y，Z を製造する場合の1日の生産額を示している。各技術者は1日に1製品しか担当できないとき，1日の最大生産額は何万円か。ここで，どの製品も必ず生産するものとする。単位　万円／日

出典　平成29年度秋期 ITパスポート試験問1

解説

問 1

错误ア
20 万日元是一种合法分配的例子,比如 A→X(6)、B→Y(6)、C→Z(8)=20,但它不是最大值,比最优解(22 万日元)低。
错误イ
21 万日元是可以达到的合计,例如 A→X(6)、B→Z(7)、C→Y(8)=21,或 A→Y(7)、B→X(6)、C→Z(8)=21,但两者都达不到最大的 22 万日元。
ウ
正解这是一个分配问题(组合最优化)。每名技术人员只负责一种产品,并且X、Y、Z 都必须生产,所以要让技术人员与产品一一对应(双射)。3 人、3 种产品,因此分配方式共有 3!=6 种。全部计算后,当 A→Z(8 万日元)、B→X(6 万日元)、C→Y(8 万日元)时,合计 8+6+8=22 万日元,这是最大值。因此正确答案是「ウ 22」。
错误エ
23 万日元在任何分配(6 种双射)下都无法达到。只看每一列(技术人员)的最大值会得到 8、7、8,但这些最大值都集中在产品 Z 上,会重复选择同一种产品,违反了约束条件。满足约束的分配上限是 22 万日元,23 万日元过高。

ここがポイント

分配问题(组合最优化):把行(产品)与列(技术人员)一一对应,使合计最大化。若只是单纯把每列的最大值相加,会重复选择同一种产品/技术人员而无法成立,所以要比较 3!=6 种分配方式,从中选出最大值。
读懂约束条件:「每名技术人员每天一种产品」并且「每种产品都必须生产」= 技术人员与产品之间的双射。在此条件下,最大合计为 22 万日元。

用語

解答問1ウ