【问题】小孩分糖

2018/3/31镜像同步12 回复

见到一个题目，想不出太好的方法，求大神指导： n个小孩，m种糖，m>n, 每种糖只有一个，要求每个小孩有且只有一个糖，每个小孩对于每种糖有不同的满意程度，小孩i对于糖j的满意程度用概率0<=pij<=1表示，一个小孩对m种糖的满意程度之和为1，求怎么分配糖使得n个小孩的总的满意程度最高？

订阅后，新回复会通过你的通知中心匿名送达。

9 条回复

xcerwww机器人#1 · 2018/3/31

m的数据范围是？

maydaygmail机器人#2 · 2018/3/31

0<n<m<100, 【在 xcerwww 的大作中提到: 】 : m的数据范围是？

unsmilecat机器人#3 · 2018/3/31

emmm,感觉是个裸的二分图带权匹配？跑一下KM或者费用流试试？不过如果这是公司的笔试面试题的话应该有更简单的办法

maydaygmail机器人#4 · 2018/4/1

对，用二分图带权的太复杂了...面试题应该有更简单的方法，没想出来... 【在 unsmilecat 的大作中提到: 】 : emmm,感觉是个裸的二分图带权匹配？跑一下KM或者费用流试试？不过如果这是公司的笔试面试题的话应该有更简单的办法

zhouliyan111机器人#5 · 2018/4/1

贪心

notahacker2机器人#6 · 2018/4/1

回复楼上。。如果一共两个小孩，3种糖，第一个小孩对糖的满意度为0.5, 0.5, 0; 第二个小孩对糖的满意度0.45, 0.45, 0.1。按照你的贪心方法，结果是第一个小孩选择第一或第二个糖，第二个小孩选第三个糖。这样好像不太对吧？不知道我有没有理解对你的方法。

w350053002机器人#7 · 2018/4/1

优先队列,根据满意度排序,其中存储[满意度,indexOfChild, indexOfCandy],每次弹出队头元素并判断该人或糖是否已经被分配,已分配的话不考虑.直到所有人都被分配过.一个很大问题在于当两个人对同一个糖有相同满意度以及两个糖对一个人有相同满意度的时候..需要把当前满意度相同的组合取出来进行dfs,数据在[0,100]可能也不会TLE吧...

duanjintao机器人#8 · 2018/4/1

指派问题

zhouliyan111机器人#9 · 2018/4/1

【在 notahacker2 的大作中提到: 】 : 回复楼上。。 : 如果一共两个小孩，3种糖，第一个小孩对糖的满意度为0.5, 0.5, 0; 第二个小孩对糖的满意度0.45, 0.45, 0.1。按照你的贪心方法，结果是第一个小孩选择第一或第二个糖，第二个小孩选第三个糖。 : 这样好像不太对吧？ : ................... n<m下要把n*m补充到m*m，补充的行按1/m补充