Algorithm to compare multiple values

Question

In my class, i have to calculate prices of 18 different building which have different prices and income. They also have changes in price when the money of quantity of the building increases.

For example: The building starts at 40 dollars when the quantity is 0. The price increments by 4 for each quantity. So if you own 1, the price to buy the next same building will be 44 in state of 40. So this is the method that will calculate the price just fine.

public float getBuildingPrice(float quantity)
    {
        float buildingNum = quantity;
        float startingPrice = 40;
        float costIncrease = 4;
        float finalPrice;

        finalPrice = startingPrice + (costIncrease*buildingNum);
        return finalPrice;
    }

The method above returns the price and i divided the calculated price with the income that comes to the building like this. 10 is the income

float storageWorth = buildingPrice/10;

The thing i am unable to do is to find out the amount of different building the user can buy in the most efficient way ( meaning highest income but lowest spending ) So it should be the lowest Price / income that should be fulfilling the condition but also keeping in mind that it must be in the budget that the user keys in. There is always a change in the price and i do not know how to compare multiple values ( 18 values ) with the extra condition to keep in the budget.

For example

Farm

Income - 1
5 buildings
Increment of 4
Price 40 + (5 * 4) = 60 Price over income = 60

Pen

Income - 5
4 Buildings
Increment of 20
Price 200 + (4 * 20) = 280 Price over income 280/5 = 56

So meaning to say the next building the user should buy is a pen because it has lower price/income. There is also chances that the price over income of both building is the same like if the building reaches 5 for pen building, both price over income of pen and farm will be 60.

@arshajii Or even better ``BigDecimal``, for storing currencies. — wassup, Aug 09 '13 at 13:13
Sounds like a [linear optimization problem](https://en.wikipedia.org/wiki/Linear_programming) to me. See http://stackoverflow.com/questions/260442/linear-programming-tool-libraries-for-java for Java libraries. — , Aug 09 '13 at 13:16
The reason i used float was because i needed decimal and big numbers. Would you mind explaining why you would choose double over float? — thhVictor, Aug 09 '13 at 13:19
@tthVictor ``double`` has twice as much precision as ``float``. ``BigDecimal`` has infinite precision. — wassup, Aug 09 '13 at 13:20
@thhVictor One variable seems to be missing. That is I guess the capital - how much a user has to make the transactions. Without that I don't know what you are trying to do. Also, when does a user make money out of owned buildings? Every 30 days, 90 days, etc? — Sajal Dutta, Aug 09 '13 at 13:21
BTW - You can do `float finalPrice = startingPrice + (costIncrease*buildingNum);` and remove the whole of the `if` statement. If `buildingNum` is zero then `costIncrease*buildingNum` will also be zero. — OldCurmudgeon, Aug 09 '13 at 13:25
@SajalDutta The building gives income at a certain time like an hour. All i want to calculate is the best income building by calculating Price of building over income so the lower the number, the better the money is spent. — thhVictor, Aug 09 '13 at 13:27
If I pay $44 for a building that has starting price $40, does it produce $10 in income or $11? Additionally, you say there are 18 values. Does this mean there are 18 different kinds of buildings, each with their own base price and cost increase? — Kevin, Aug 09 '13 at 13:40
@Kevin Yes for example a farm building has base price of 40, income of 1 and increment by 4 whereas a pen has base price of 200, income of 5 and increment of 20 and also it will product an income 11 if you have two pen and 1 farm — thhVictor, Aug 09 '13 at 13:46
Don't people usually use `long` for money, due to its being discrete? — G. Bach, Aug 09 '13 at 14:17
Can anyone who claims that this can be done with linear constraints give a linear program for this problem? I can't come up with one myself. — G. Bach, Aug 09 '13 at 15:02

Tarik · Answer 1 · 2013-08-09T18:10:56.143

2

This is a formulation of your problem that ends up a mixed integer and non linear programming problem:

For all building type i let's define:

Pi : price of building type i
Ci : Price increment of building type i
Mi : income for building type i
B : Budget
Ni : Number of buildings of type i purchased.

Purchasing Ni building of type i equals:

Sum for j=1 to Ni    Pi + (j - 1) × Ci = Ni (Pi + ( Ni - 1) / 2 × Ci)

Mixed integer non linear programming formulation:

Maximise Sum for i     Ni × Mi

Subject to : sum for i    Ni (Pi + (Ni - 1) / 2 ×Ci) <= B

Note that Pi, Ci, Mi and B are constants. Decision variables are Ni

An other solution is to purchase a building at a time selecting the one with the maximum income per invested money as per the following ratio:

Mi / (Ni (Pi + ( Ni - 1) / 2 × Ci))

At each step you calculate the building with the maximum ratio, purchase a building, deduct the price of the budget and repeat until the budget is exhausted. I do not have a proof that you will get an optimum my following this algorithm.

Third solution pseudocode (brute force):

(income, index_list) function maximize_income(i, b)
   if i > last_building_type
       return 0, []
   endif
   max_income = 0
   max_income_index = 0
   while b >= P(i) - (j-1) * C(i)
       b = b - P(i) - (j-1) * C(i)
       (income, index_list) = maximize_income(i+1, b)
       income = income + j * M(i) 
       if income > maximum_income
           maximum_income = income
           maximum_income_index = j
       endif
   endwhile
   add maximum_income_index to index_list
   return maximum_income, index_list
end function

index_list is an array containing the number of each type of building

edited Aug 09 '13 at 18:10

answered Aug 09 '13 at 14:27

Tarik

10,810
2
26
40

I have no knowledge about linear programming. How do i go about doing this? – thhVictor Aug 09 '13 at 14:39
As you said, this is non-linear. Your last paragraph still states linearity. – G. Bach Aug 09 '13 at 15:03
@G. Bach I initially thought it was linear but after formulating, I found out that it was a mixed integer non linear problem. Thanks for pointing this out. – Tarik Aug 09 '13 at 15:34
@Tarik I realize I'm nitpicking really hard now, but your answer still says "Linear programming formulation:" in its first half. – G. Bach Aug 09 '13 at 17:00
@G. Bach Appreciate your comment. Fixed the offending title. From past experience I dealt with MIPS and non-linear solvers in the context of non-linear programming. These MIPS and non linear capabilities seem to have come as extensions to what originally were linear programming packages. I might be wrong though :-) – Tarik Aug 09 '13 at 18:19
@Tarik That is very well possible, I played around with general constraint solvers myself once, and it does seem that at they are related. I have no idea about the complexity of non-linear constraints though, even assuming rational domains for the solution variables. – G. Bach Aug 09 '13 at 18:23
b >= P(i) - (j-1) * C(i) is j the number of building of the same type? and what is maximum_income and maximum_income_index? – thhVictor Aug 10 '13 at 17:48
Yes, j is the number of buildings of the same type. maximum_income is the maximum income you get out of the budget b that was passed as a parameter, by purchasing j buildings of type i then recursively calling maximum_income with the remaining budget to find out what income can be generated out of the remaining budget. maximum_income_index is a misnomer, it represents the number of buildings of type i that generates the maximum income. – Tarik Aug 10 '13 at 18:20

score 0 · Answer 2 · answered Aug 09 '13 at 14:17

Your problem is a linear programming problem. Such problems don't have easy answers.

To solve such problems, people have invented many smart algorithms like the Simplex Algorithm.

These alogrigthms work on a represenation of the problem that basically is a set of mathematical linear equations. You have to think hard about your problem and formulate these equations.

A C library to solve a LP problem forumlated this way is the GLPK (GNU Linear Programming Kit). There are frontends for Python and for Java.

Your question is not a programming problem. It is a mathematical problem that can be solved in any language. Give enough time, it can even be solved on paper.

Algorithm to compare multiple values

2 Answers2