Forum

> > Off Topic > Lua Algorithmic Tutorial
Forums overviewOff Topic overviewLog in to reply

English Lua Algorithmic Tutorial

3 replies
To the start Previous 1 Next To the start

old Lua Algorithmic Tutorial

Lee
Moderator Off Offline

Quote
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?

old Re: Lua Algorithmic Tutorial

DannyDeth
User Off Offline

Quote
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.

old Re: Lua Algorithmic Tutorial

Lee
Moderator Off Offline

Quote
@user 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

@user 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.
To the start Previous 1 Next To the start
Log in to replyOff Topic overviewForums overview