Off Topic Lua Algorithmic Tutorial
Lua Algorithmic Tutorial
3 AntwortenLee Moderator 
Offline
Suppose that you are the owner of a large restaurant chain with 10 or so stores and it's that time of the year when you want to renovate your business, but you only have 20 million dollars to divide between these 10 stores.
Now you told each of these stores to draw up 3 plans, each costing c[i] million dollars and will generate an estimate of r[i] amount of revenue. If each store may at the very most implement only 1 of its 3 plans, figure out a way to maximize the profit between all of these stores.
Furthermore, can you figure out a way to efficiently solve the problem with 10000 stores and up to 10 plans each? vyn BANNED Offline
Quick question: are "upgrade" or "contruction" times included in this problem?
EDIT: Also, the revenue == total revenue over the year?
EDIT2: I take only one of the plans for each store may be used, common sense. Lee Moderator Offline
@
vyn:
That's right, it's NP complete as both verification and solution runs in exponential search space naively, however the solution can be expressed in O(n^2) search space given the correct order of evaluation since the cost function monotonically increases 
@ DannyDeth:
Assume that all renovations are made instantaneously. Revenue = amount of money generated not including the cost of the plan, however it's also acceptable to assume that revenue is the net profit including the cost of the plans. 
1 
