Algorithm for the maximum items that can be purchased, taking into account price increases with an interval of N
I was looking at the question posted here:
Algorithm for calculating the total cost in groups of N
and wondered how to determine the maximum items that could be bought, given the cost, which increases by X for every N items.
For example, if I have $ 20 and want to buy something that starts at $ 1, but for every fifth item (for example, $ 1), then I can purchase 11 of them, with $ 2 left (five in $ 1 + five at $ 2 + one at $ 3 = $ 18).
Is there a formula that can be used to solve this problem?
source to share
I will explain a simpler option, when we start at 1 and increase by 1 times n times. Here we need n
for the first n
elements, 2n
for the next elements n
, etc. Suppose we can get the maximum of k
complete groups (the whole element is a multiple n
). So our total cost will be
n + 2*n + 3*n + ...+ k*n
This must be less than S. So
(1 + 2 + .... + k) * n <= S
=> k * (k+1) * n / 2 <= S
=> n * k ^ 2 + n * k - 2 * S=0
Solving for k we get
k = (-n + sqrt(n ^ 2 + 8 * n * S )) / (2 * n) // take floor value
So now the amount of money left
S1 = S-(n * k * (k + 1)) / 2
And the number of items we can still buy is
a = S1 / (k + 1)
Total number
k * n + a
The rest of money -
S1 mod (k + 1)
For example with S = 20
andn = 5
k = (-5 + sqrt(5 ^ 2 + 8 * 5 * 20))/(2 * 5) = 2.37 = 2 // floor S1 = 20 - ( 5 * 2 * 3) / 2=5 a = 5 / (2 + 1)=1.66.. = 1 //floor total = 2 * 5 + 1 = 11 money left = 5 mod 3 =2
Similarly, you can get the general formula when you start with a
and increase the value x
every n
time. In this case, k should be
k = (sqrt(((x - 2 * a) * n) ^ 2 + 8 * n * x * S) + (x - 2 * a)* n) / (2 * n * x)
v = a + k * x
S1 = S - (2 * a + (k - 1) * x) * k * n / 2
y = S1 / v
total = k * n + y
left = S1 mod v
source to share
Let the base price first, after k patches buying the price,
...
Let the purchase cost of the first k patches be F (k), then
Let M be the money you have, most of the patches you can buy k * satify
After purchasing k * patches, you can also buy the remaining
elements.
So the common item you can buy is: k * + r *.
I'm sure this is the formula you would expect :-).
source to share