作者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