作者barry800414 (小铭)
看板b98902HW
标题[问题] 数学问题
时间Fri Oct 1 02:37:38 2010
现在有100个顾客 对於ABCDE五种商品喜好顺序由最喜欢排到最不喜欢(1~5)
每个不一定相同 可是现在ABCDE商品有数量限制 已知 A+B+C+D+E = 100
ex A容量20 B容量25 C容量15 D容量20 E容量20
Q: 如何分配商品使得顾客满意度最高呢?
(假设满意度高代表买到的商品喜好顺序加总越低)
这是NP问题吗? 还是可以用greedy?
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.243.226
1F：推 s864372002:直觉是flow... 10/01 08:55
2F：推 iForests:你可以找一下 min-cost max-flow 的资料 10/01 13:46
3F：推 robertabcd:选课志愿问题(咦) 10/01 15:05
4F：推 hsh2009:为什麽我会觉得很像经济学的问题... 10/02 00:57
5F：推 DerekB98126:我都觉得是经济学的问题... 10/02 16:07
6F：推 paul112004:我第一直觉是比较利益原则…… 10/02 17:55
7F：推 s864372002:source流到100个顾客，容量皆为1，cost不重要； 10/02 19:22
8F：→ s864372002:100个顾客分别流到5样商品，容量皆为1，cost为喜好序； 10/02 19:23
9F：→ s864372002:5样商品皆流到sink，容量为商品数量，cost不重要。 10/02 19:24
10F：→ barry800414:谢谢 不过我还是不会Q_Q 10/04 12:41