0

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.

Improve this question
13
  • 2
    You should really use doubles instead of floats. Commented Aug 9, 2013 at 13:06
  • 2
    @arshajii Or even better BigDecimal, for storing currencies. Commented Aug 9, 2013 at 13:13
  • 3
    Sounds like a linear optimization problem to me. See stackoverflow.com/questions/260442/… for Java libraries. Commented Aug 9, 2013 at 13:16
  • 2
    @tthVictor double has twice as much precision as float. BigDecimal has infinite precision. Commented Aug 9, 2013 at 13:20
  • 1
    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. Commented Aug 9, 2013 at 13:25

2 Answers 2

Reset to default
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

Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

I have no knowledge about linear programming. How do i go about doing this?
As you said, this is non-linear. Your last paragraph still states linearity.
@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 I realize I'm nitpicking really hard now, but your answer still says "Linear programming formulation:" in its first half.
@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 :-)
|
0

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.