Learn the fundamentals of the popular programming language JavaScript so that you can explore the realm of web development.

In a previous question we're shopping for an ingredient which comes in standard pack sizes of either 100g, 250g or 500g, having prices $0.40, $0.75 and $1.00 respectively.

Let:

PackSize = {100; 250; 500}

PackPrice = {0.40; 0.75; 1.00}

QuantityNeeded = {0.... up in steps of GCD(PackSize)... MaxQuantity }

GCD = greatest common divisor, eg GCD({100; 250; 500}) = 50

We only need to define a table with intervals in these steps as in between there won't be any change in the cost. I think this logic is right, please correct me if wrong.

We then define f_mincost(QuantityNeeded ) as the set of packs that meets the QuantityNeeded at minimum cost, eg:

f_mincost(1050) gives 1 x 100g + 2 x 500g at a total cost of $2.40

This problem is solved in the previous question by using dynamic programming to create a lookup table of values:

a) Quantity needed, eg 1050

b) Minimum cost, eg $2.40

c) Pack selection, eg 100, 500, 500

Questions:

1. What MaxQuantity do we need to tabulate upto before the pattern is repeating

ie MaxQuantity = some function of Packsize

2. How can we define f_mincost(QuantityNeeded) as a function of this repeating pattern

eg what is f_mincost(6400) as a function of f_mincost(some value <= MaxQuantity)

This is is probably straightforward but after the previous question my head has been frazzled!

Thanks again

Let:

PackSize = {100; 250; 500}

PackPrice = {0.40; 0.75; 1.00}

QuantityNeeded = {0.... up in steps of GCD(PackSize)... MaxQuantity }

GCD = greatest common divisor, eg GCD({100; 250; 500}) = 50

We only need to define a table with intervals in these steps as in between there won't be any change in the cost. I think this logic is right, please correct me if wrong.

We then define f_mincost(QuantityNeeded ) as the set of packs that meets the QuantityNeeded at minimum cost, eg:

f_mincost(1050) gives 1 x 100g + 2 x 500g at a total cost of $2.40

This problem is solved in the previous question by using dynamic programming to create a lookup table of values:

a) Quantity needed, eg 1050

b) Minimum cost, eg $2.40

c) Pack selection, eg 100, 500, 500

Questions:

1. What MaxQuantity do we need to tabulate upto before the pattern is repeating

ie MaxQuantity = some function of Packsize

2. How can we define f_mincost(QuantityNeeded) as a function of this repeating pattern

eg what is f_mincost(6400) as a function of f_mincost(some value <= MaxQuantity)

This is is probably straightforward but after the previous question my head has been frazzled!

Thanks again

Do more with

EXPERT OFFICE^{®} is a registered trademark of EXPERTS EXCHANGE^{®}

f_mincost(6400) = ?

Divide 6400 by the largest size , 500 , and get a quotient, Q, and remainder, R:

Q(6400/500) = 12

R = 6400 - (12 * 500) = 6400 - 6000 = 400

From this first step, you need to buy 12 orders of size 500g for a cost of 12 * $1 = $12

You still need to order 400g. (I would round up and just get 13 orders for a cost of $13 and store a away the extra 100g; but I'll assume you have no storage space.)

Divide 400 by the next largest size, 250, and get a quotient, Q, and remainder, R:

Q(400/250) = 1

R = 400 - (1 * 250) = 400 - 250 = 150

This second step, you need to buy one order of size 250g for cost of 1* $0.75 = $0.75

You still need to order 150g.

Divide 150 by the next largest size, 100, and get a quotient, Q, and remainder, R:

Q(150/100) = 1

R = 150 - (1 * 100) = 150 - 100 = 50

Since there are no package sizes smaller than 100, you need to round up and purchase two orders of 100g for a cost of 2 * 0.40 = $0.80.

Your total cost is $12 + $0.75 + $0.80 = $13.55 and you have 50g left over to throw away.

Notice that the actual

https://en.m.wikipedia.org/wiki/Linear_programming

Linear programming (LP, also called linear optimization) is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming (mathematical optimization).

More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints. Its feasible region is a convex polytope, which is a set defined as the intersection of finitely many half spaces, each of which is defined by a linear inequality. Its objective function is a real-valued affine (linear) function defined on this polyhedron. A linear programming algorithm finds a point in the polyhedron where this function has the smallest (or largest) value if such a point exists.

Here is an entire course on linear programming . It consists of 27 lectures each is about 1 1/4 hours long.

https://m.youtube.com/watch?v=FdKgeeb4q3w 1. Skip the first 9.5 minutes

https://m.youtube.com/watch?v=xY6AlnGZ1bw. 2

https://m.youtube.com/watch?v=N4GxD63lqLc. 3

https://m.youtube.com/watch?v=NYZ206ccuzY. 4

https://m.youtube.com/watch?v=cvRWORxDAY8. 5

https://m.youtube.com/watch?v=reswxUMC0iM. 6

https://m.youtube.com/watch?v=i4ig7Cpravo. 7

https://m.youtube.com/watch?v=kh2qKN1jEAA. 8

https://m.youtube.com/watch?v=CiLG14fsPdc. 9

https://m.youtube.com/watch?v=kvIp2CfFDUQ (ruined version) 10

https://m.youtube.com/watch?v=_uhTN6KvCC8. 10

Here is a very short introduction to linear programming:

https://m.youtube.com/watch?v=gbL3vYq3cPk

Sorry I gave you that was my suggestion. I was just demonstrating that for this instance we have a solution using this approach. In general, the solution is solved using LP.

>> You refer to LCM. I don't believe that has any value

I was thinking in the more general cases of arbitrary numbers. For example, LCM( 25, 49, 81) = 99225. I don 't see how this number is going to help you. Granted in specific cases, there may be some optimizations when using the LCM that you notice to help, but not in a formulation.

I also believe that patterns may only be meaningful in very specific cases, but not in general.

My belief is that in the general case of an arbitrary number of variables (your OP shows 3, which is beyond the scope of the first couple of lectures) and a set of constraints, then this problem is already solved, and there are entire semesters to explain how to solve them.

>> From tests done so far I believe this solution is complete. I will try to demonstrate this before closing this question.

I look forward in seeing your demo for arbitrary number of variables and values.

## Premium Content

You need an Expert Office subscription to comment.Start Free Trial