[問題] facebook模擬城市(My City)的問題

看板Prob_Solve (計算數學 Problem Solving)作者 (阿哲是我 我是哲阿)時間15年前 (2009/09/11 02:51), 編輯推噓5(504)
留言9則, 6人參與, 最新討論串1/2 (看更多)
在My City遊戲中,城市有 8 項要素 分別為 繁榮,安全,勞動,文化,科學,娛樂 和 健康 每一天可以增加一個市民 新增不同職業的市民會對城市素質有不同的要求條件(條件滿足才能新增該類市民) 不同職業的市民會對城市有不同影響,但人口數固定+1 現在給定 8 項要素的值 和 一個想要新增的職業 想要知道最快滿足該職業新增條件的作法(新增的順序)。 請問解題的大致想法? 我想了幾小時沒有想到適合的Orz 下面每一行是 市民職業,對7項素質的影響力,對8項素質的需求條件 市民 ,繁,安,勞,文,科,娛,健,人口 ,繁榮 ,安全,勞動,文化,科學,娛樂,健康 律師 ,+2,+1, , , ,-2, , ,>40 , , , , ,>40 , 乞丐 ,-1,-1, , , , ,-1, ,>-10 , ,>15 , , , , 小丑 ,-1, , , , ,+1, , , , , , , ,<0 , 學生 ,-1,+1, , ,+1,+1, ,<200 , , ,<40 , ,>-5 , , 祭司 , , , ,-1,-2, , , , , , ,>-5 ,>15 , , 駭客 ,-1,-2, , , ,+1, , ,>15 , , , ,>5 , , 警官 , ,+2, , , , , , , ,<15 , , , , ,>-10 特工 , ,-2, , ,+2, , , , ,<-10, , ,>15 , , 棋王 , , , , ,+5, , ,>800 ,>500 , , , ,<50 , , 毒販 , ,-1, , , , ,-2, , ,>15 , , , , ,>-10 商人 ,+2, , , , , , , ,<-10 , ,<15 , , , , 酒保 ,-1,-1, ,+1, ,+1, , ,>200 , , ,>400, ,<200, 社工 , ,+2,+2, , , , ,>800 , ,<0 ,>200, , , , 法官 ,-1,+2,+2, , , , ,>300 ,<300 ,>100,<200, , , , 按摩師 , , , ,-1, ,+1,+1, , , , ,>60 , ,>60 ,>50 太空人 ,-2, , , ,+3, ,+1, ,>1000, , , ,<100, ,>400 出版商 , , , ,+2,-1, , , , , , ,>60 ,>80 , , 理髮師 , , , , , ,+2,-1, , , ,>60 , , ,>30 ,>40 消防員 , ,+2, , , , ,+1, , ,<15 , , , , ,<-10 會計師 ,+1, ,+1, , ,-1, , , , , , , ,>0 , 盜墓者 , ,-2, ,-1, , ,-1,>300 , , , ,<400, , ,>100 狗仔隊 , ,-1, ,-1, ,+2, ,>300 , , , ,>100, ,>100, 算命仙 , , , ,-1,-1, , ,>300 ,<600 , , ,>200, , , 建築學家 ,+1,-1, ,+2,-1, , , , ,>40 , ,>50 ,<120, , 火箭專家 , , , , ,+3, ,-1,>300 ,>300 , , , ,>200, ,>300 水管工人 , , ,+1, ,+1, ,+1, , , , ,>-5 ,<15 , , 山水畫家 , , , ,+2, , ,+1, , , , ,<-5 ,>15 , , 工廠工人 , , ,+2, , , , , ,>-10 , ,<15 , , , , 工廠經理 ,+2, , , ,+1, , , ,<-10 , ,>15 , , , , 飛機技師 , , ,+2, ,+1, , ,>20 , ,>5 ,<50 , ,>10 , , 整形醫師 , , , , ,-2,+1,+2, , , , , ,>50 ,>60 , 壽司師傅 , , , ,+2, ,+1, , , , , ,<300, , ,>300 電視演員 , , ,-1,+1, ,+1, , , , , ,<-5 ,<15 , , 脫衣舞孃 , , ,-2, , ,+2, , , , ,>40 , , ,>45 , 連環殺手 , ,-2,-1, , , ,-1,>10 , ,>10 , , , , , 奧運選手 ,+1, , ,+1, ,+2, , ,>50 , , , , ,<550,>300 恐怖份子 ,-2,-1, , , , , , ,>-10 , , , , , , 核工程師 ,+1, , , ,+2, ,-1,<250 ,<50 ,<50 , , ,>10 , , 私家偵探 , ,+2, , , ,+1, , , ,<160, ,>45 , , , 考古學家 , , ,-1,+1,+2, , ,>300 ,<600 , ,>150,<250,<300, , 住院醫師 , ,+1, , ,+1, ,+1, , , ,>0 , ,>0 , ,<40 搖滾明星 ,+1, , ,+2, , , , , , ,>20 ,<40 , , , 空手道家 , ,+1, ,+1,-1, ,-1, ,>35 , , , , , ,>50 前蘇聯特工 , ,+2, , ,+1, , ,>20 ,<-10 , , , ,<20 , , 認知工程師 , , , , ,+1,+2, ,<300 , , , , ,>-5 ,<25 , 計程車司機 ,+1, ,+1,-1, ,+1,+1, ,>35 , ,>45 , , ,<160,<60 器官交易者 ,+2, , , , , ,+1,>20 ,<40 , ,>10 , , , ,>-10 撲克牌玩家 , ,-2, ,+2, ,+1, , , , , ,<130, ,>50 , 黑手黨教父 ,-2,-1,+2, , , , ,>3000,>400 ,<300,>100, , , , 房地產經紀 ,+1,-2, , , , , ,>300 ,>600 ,>200,>300, , , , 披薩快送員 ,-1, ,+2, , ,+1, ,>200 , , ,<100,<100, , , 明星的保鑣 , ,+2, ,-1, ,+2, , ,<400 , , ,>500, ,>200, Facebook迷 , , ,-2, ,+1,+1, , , , ,>60 , ,>55 ,>65 , 停車收費員 , ,+1, , , ,-1, ,>300 ,<400 ,>100, , , , , 啦啦隊隊長 , , , , , ,+2,+1, , ,>300, , , ,<150, 財務分析師 ,+4, , , ,+1, , ,>800 ,<100 , ,>300, , , , 婦產科醫師 , , , , , , ,+3,>400 ,>200 , , , , , ,<100 高爾夫球手 ,+2, , , , ,+1, , ,>45 , , , , ,<65 , 服裝設計師 ,+1, ,-1,+1, , , , ,>400 , ,>200, , , , 法式麵包師 , , , ,+2,-2, ,+1, ,>40 , , ,<160, , , 一般診斷醫師 , , , , ,+1, ,+2, , ,>15 , , , , ,<-10 手足球的精英 ,-1, , , , ,+3, ,>400 ,>300 , , , , ,<400, 複製人科學家 , , , ,-3,+3, , , ,>400 , , ,>400,<300, ,>100 神經外科醫師 ,+1, , , ,+1, ,+2,<300 , , , , ,>10 , ,<20 美國超偶歌手 , , , ,-1, ,-2, ,>20 , , ,>5 , , ,>10 , 無政府主義者 ,-1,-1,-1,+1, , , , , , ,>20 , , , , 反基因改造活動, , , , ,-3, ,+1, , , , , ,>110, , 喝醉了的英式橄, , , ,+2, ,-1, ,>10 , , , , , ,>10 , 瞞天過海第六集, , , , , ,+2, ,>10 , , , , ,>15 ,<40 , 抑鬱的數學教師, , , , ,+2,-1, ,<200 , , , , ,<30 ,>-10, 華麗的說唱歌手,+1, , ,+2, , , , , , ,>15 ,<30 , ,>10 , 波蘭伏特加蒸餾,+1, ,+2, , , , ,>10 ,<20 , , , , ,>5 , 瘋狂的病毒學家, ,-1, , ,+1, ,-2,>10 , , , , ,>15 , ,>-20 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.47.65.152

09/11 10:38, , 1F
線性規劃..
09/11 10:38, 1F

09/11 17:09, , 2F
線性規劃?不過這題還有順序問題耶..
09/11 17:09, 2F

09/12 12:14, , 3F
順序問題應該linear programming 可以處理吧
09/12 12:14, 3F

09/12 12:15, , 4F
不過要最快的次序我就不確定了.. 可是還是可以朝這方向查查看
09/12 12:15, 4F

09/13 06:09, , 5F
可以考慮從shortest path的方向去想
09/13 06:09, 5F

09/13 11:15, , 6F
用動態規劃應該是解的出來 至於更有效率的方法就要想
09/13 11:15, 6F

09/13 17:35, , 7F
有趣的問題 XD 我也來想
09/13 17:35, 7F

09/13 17:57, , 8F
嗯,想來想去還是暴力法硬幹 XD
09/13 17:57, 8F

09/16 19:46, , 9F
BFS下去吧!
09/16 19:46, 9F
文章代碼(AID): #1AgKgK52 (Prob_Solve)
文章代碼(AID): #1AgKgK52 (Prob_Solve)