機台購買問題 - 拼圖

這是由最近碰的幾個小遊戲, 將核心問題簡化後的版本

想了一想之後, 覺得好像沒有簡單的做法, 所以想打上來跟大家討論

------------------------------------------------------------

假定你是一家工廠的老闆, 擁有 N 塊可以放置機器的地點, 每塊都恰能放一台機器

已知有幾種生產機器, 每種機器有他的建置成本(元)與生產速度(元/天)

拆除與回收成本為了計算方便, 都假定為零, 建置所需時間也假設為零


你現在有一筆初始的資金 M , 當然 M 至少要大於最便宜的生產機器

目標是要讓 N 塊地都放滿機王, 也就是生產速度最快的機器

為了簡化計算, 而且工廠工人也要休息,

假定每次做機器購買決策, 距開始時間為整數天 (即生產天數為離散, 不用考慮小數)

請問要如何設計演算法, 讓這個目標最快達成?

※ 編輯: walkwall 來自: 59.127.189.54 (02/14 03:08)