# Thread: Packs for Given Quantity

1. ## Packs for Given Quantity

This is probably the simplest question asked on the forum, but here goes.

Assume the following

Product 1 comes in any of the following two packs

pack of 3
or
pack of 5

Product 2 comes in any of the following three packs
pack of 3
or
pack of 5
or
pack of 8

How do i calculate the following?

Given a quantity of 10 from Product 1 i want the result to be
2 x 5

Given a quantity of 14 of Product 2 i want the result to be
1 x 8
3 x 2

It is probably something very simple but my poor brain does not grasp maths at all.

Thanks

2. Originally Posted by habla
Product 1 comes in any of the following two packs

pack of 3
or
pack of 5

Product 2 comes in any of the following three packs

pack of 3
or
pack of 5
or
pack of 8

How do i calculate the following?

Given a quantity of 10 from Product 1 i want the result to be
2 x 5

Given a quantity of 14 of Product 2 i want the result to be
1 x 8
2 x 3
It looks like you have already done what you want. Are you trying to ask a general question?

Maybe you're thinking of something like, "Given some specified quantity of product, state the number and kind of packages in order to acquire the specific quantity".

I'm not sure what you're trying to do, yet. Please provide more detail.

PS: I commuted the positions of your 3×2 above because 2×3 follows the convention that you wrote for the others. That is:

2 × 5 means "two packages of 5"
1 × 8 means "one package of 8"

3 × 2 means "three packages of 2", but product 2 does not come in packages of 2.

2 × 3 is better: "two packages of 3"

3. Hi @mmm444bot

It appears i did not make it clear indeed sorry about that.

You did guess correct.

I want to provide the quantity and get the package combination based on the provided packages.

So the Input will be 10 qty and the result 2 x 5 "two packages of 5"

Thanks

4. Originally Posted by habla
I want to provide the quantity and get the package combination based on the provided packages.

So the Input will be 10 qty and the result 2 x 5 "two packages of 5"

Thanks
This is not something a formula could do for you; it's an algorithm. If you want to write a program to do this, we might be able to help; but basically it will amount to trial and error. And you might work it out by examining how you found the sample answers you gave. If you aren't programming, a careful description of what you did (generalized) would be an answer!

It's also worth noting that sometimes there will be no solution (e.g. if you need 4 for your examples); and sometimes there will be more than one, so you might want to find the solution that uses the fewest packages (or costs least).

One approach would be to use something reminiscent of the "greedy algorithm": try using the largest packages first, then back down and use smaller packages if necessary.

5. I am trying to achieve that result using javascript actually. I was thinking there will be a magical formula where i can put in the Qty and loop through an Array. But as you see i am not that good with Maths.

It will be nice if you can give me some guidance on how to do this in the most efficient way in Javascript or any other programming language.

Cheers,

6. Habla

It appears to me that you can solve the problem for product I in a fairly simple way, but I have not yet been able to construct a proof. While I work on a proof, I shall give you my proposed but unproven solution. If it works, a similar but more complex solution will almost certainly work for product II. As Dr. Peterson said, the solution is an algorithm.

Let n be the number of items to be packaged so n must a positive integer.

Let x and y be the number of 5-item packages and 3-item packages respectively. We want to find x and y such that (1) 5x + 3y = n, meaning that the packages will hold exactly n items, and (2) x + y is minimized, meaning no other combination of packages holding n items has a fewer number of packages. Consequently, x and y must both be non-negative integers.

Also as Dr. Peterson said, there are no solutions if n = 1, 2, 4, or 7. I believe (but have not yet proved) there is always a solution if n > 7.

So compute

$k = \left \lfloor \dfrac{n}{5} \right \rfloor.$

I have no idea how to program that in javascript. In the old days, you would just divide 5 into n avoiding floating point arithmetic. What the notation means is to ignore all digits to the right of the decimal point. We are getting the integer portion of the quotient.

$\therefore n = 5k + m \text {, where } m \text { is an integer such that } 0 \le m \le 4.$

$m = 0 \implies x = k \text { and } y = 0 \implies x + y = k.$

$m = 1 \implies x = k - 1 \text { and } y = 2 \implies x + y = k + 1.$

$m = 2 \implies x = k - 2 \text { and } y = 4 \implies x + y = k + 2.$

$m = 3 \implies x = k \text { and } y = 1 \implies x + y = k + 1.$

$m = 4 \implies x = k - 1 \text { and } y = 3 \implies x + y = k + 2.$

Notice that you need at least k packages (obviously) but never more than k + 2 packages. On average, you will need 1.2 packages.

Now all I have to do is to prove it.

7. Originally Posted by habla
I want to provide the quantity [and product type] and get the package combination based on the provided packages.

So the Input [could] be 10 qty [and 1 type] and the result 2 x 5 "two packages of 5"
If an input for product type 1 were 26, would you want the output to be:

2×3 + 4×5

or are you seeking results comprised of one package size only (not combinations of package sizes)?

If it's the latter, then 26 would be an invalid entry for product type 1.

You could write a loop, and use the % operator to test cases. This operator gives the remainder, after dividing one number (the dividend) by another (the divisor).

26%3 returns 2 because that's the remainder left, after dividing out eight 3s from 26 (i.e., 8×3+2=26).

24%3 returns 0 because there's no remainder left, after dividing out eight 3s from 24 (i.e., 8×3+0=24).

In other words, the % operator can be used to determine whether a given divisor divides a particular dividend "evenly" (no remainder).

Using a loop, we could subtract multiples of 5 from 26, and check each difference for divisibility by 3.

(Symbol means 'therefore')

26 - 0×5 = 26 then 26%3 ≠ 0 packages of 3 only won't work

26 - 1×5 = 21 then 21%3 = 0 7×3 + 1×5

26 - 2×5 = 16 then 16%3 ≠ 0 packages of 3 won't work with 2×5

26 - 3×5 = 13 then 13%3 ≠ 0 packages of 3 won't work with 3×5

26 - 4×5 = 6 then 6%3 = 0 2×3 + 4×5

26 - 5×5 = 1 packages of 5 only won't work

Does this example help?

8. I have a proof, but it is hardly elegant. But it turns into a fairly simple procedure, which is easily extended to product II.

$n \text { is a positive integer.}$

$\text {DEFINE: } k = \left \lfloor \dfrac{n}{5} \right \rfloor \text { and } m = n - 5k.$

$\therefore k \text { and } m \text { are integers, } n = 5k + m \text {, and } m = 1,\ 2,\ 3,\ \text { or } 4.$

$\text {DEFINE integers } x \text { and } y \text { such that (i) } 5x + 3y = n \text {, (ii) } x \ge 0 \le y \text {, and}$

$\text {(iii) if integers } a \text { and } b\ \exists \text { such that}$

$\text{(1) } 5a + 3b = n \text { and ( 2) } 0 \le b \ne y \text {, then } a + b > x + y.$

Note that x and y may not exist for every value of n.

We need three lemmas. LEMMA 1 states that if y exists, then y = 0, 1, 2, 3, or 4. Proof follows.

$\text {ASSUME non-negative integers } x \text { and } y \ \exists \implies 5x + 3y = n.$

$\text {ASSUME } y \ge 5.$

$\text {Let } a = x + 3 \text { and } b = y - 5 \implies a \text { and } b \text { are integers such that }$

$5a + 3b = 5x - 15 + 3y + 15 = 5x + 3y = n \text { and } 0 \le b \ne 5.$

$\text {By definition then, } a + b > x + y.$

$\text {BUT } a + b = (x + 3) + (y - 5) = (x + y) - 2 < x + y \text {, a CONTRADICTION.}$

$\therefore y \not \ge 5 \implies y = 0,\ 1,\ 2,\ 3, \text { or } 4\ \because \text { by definition } y \text { is an integer } \ge 0.$

LEMMA 2 states that if x exists, it does not exceed k. Proof follows.

$\text {ASSUME non-negative integers } x \text { and } y \ \exists \implies 5x + 3y = n.$

$\text {ASSUME } x \ge k + 1 \implies 5x + 3y \ge 5(k + 1) + 3y \implies n \ge 5k + 5 + 3y \implies$

$5k + m \ge 5k + 5 + 3y \implies 0 > m - 5 \ge 3y \implies y \not \ge 0\ \because \ m \le 4.$

$\text { BUT, by definition } y \ge 0 \text {, a CONTRADICTION.}$

$\therefore x \not \ge k + 1 \implies x < k + 1 \implies x \le k\ \because \text { by definition } x \text { is an integer.}$

LEMMA 3 states that if x exists, it is k - 2, k - 1, or k. Proof follows.

$\text {ASSUME non-negative integers } x \text { and } y \ \exists \implies 5x + 3y = n.$

$\text {ASSUME } x \le k - 3 \implies 5x + 3y \le 5(k - 3) + 3y \implies n \le 5k - 15 + 3y \implies$

$5k + m \le 5k - 15 + 3y \implies 15 \le m + 15 \le 3y \implies 5 \le y\ \because \ 0 \le m.$

$\text {BUT, by LEMMA 1, } y \le 4 \text {, a CONTRADICTION.}$

$\therefore x \not \le k - 3 \implies x > k - 3 \implies x \ge k - 2\ \because \text { by definition } x \text { is an integer.}$

$\text {By LEMMA 2, } x \le k \implies x = k - 2,\ k - 1, \text { or } k \ \because \text { by definition } x \text { is an integer.}$

Putting our lemmas together, there are exactly fifteen potential possibilities, and, by brute force, we can find x and y (if they exist) by examining all fifteen of them.

$\text {I: } x = k - 2 \text { and } y = 0 \implies n = 5x + 3y = 5k - 10 \implies m = -\ 10 \text { FALSE.}$

$\text {II: } x = k - 2 \text { and } y = 1 \implies n = 5x + 3y = 5k - 10 + 3 \implies m = -\ 7 \text { FALSE.}$

$\text {III: } x = k - 2 \text { and } y = 2 \implies n = 5x + 3y = 5k - 10 + 6 \implies m = -\ 4 \text { FALSE.}$

$\text {IV: } x = k - 2 \text { and } y = 3 \implies n = 5x + 3y = 5k - 10 + 9 \implies m = -\ 1 \text { FALSE.}$

$\text {V: } x = k - 2 \text { and } y = 4 \implies n = 5x + 3y = 5k - 10 + 12 \implies m = 2 \text { OK.}$

$\text {VI: } x = k - 1 \text { and } y = 0 \implies n = 5x + 3y = 5k - 5 \implies m = -\ 5 \text { FALSE.}$

$\text {VII: } x = k - 1 \text { and } y = 1 \implies n = 5x + 3y = 5k - 5 + 3 \implies m = -\ 2 \text { FALSE.}$

$\text {VIII: } x = k - 1 \text { and } y = 2 \implies n = 5x + 3y = 5k - 5 + 6 \implies m = 1 \text { OK.}$

$\text {IX: } x = k - 1 \text { and } y = 3 \implies n = 5x + 3y = 5k - 5 + 9 \implies m = 4 \text { OK.}$

$\text {X: } x = k - 1 \text { and } y = 4 \implies n = 5x + 3y = 5k - 5 + 12 \implies m = 7 \text { FALSE.}$

$\text {XI: } x = k \text { and } y = 0 \implies n = 5x + 3y = 5k \implies m = 0 \text { OK.}$

$\text {XII: } x = k \text { and } y = 1 \implies n = 5x + 3y = 5k + 3 \implies m = 3 \text { OK.}$

$\text {XIII: } x = k \text { and } y = 2 \implies n = 5x + 3y = 5k + 6 \implies m = 6 \text { FALSE.}$

$\text {XIV: } x = k \text { and } y = 3 \implies n = 5x + 3y = 5k + 9 \implies m = 9 \text { FALSE.}$

$\text {XV: } x = k \text { and } y = 4 \implies n = 5x + 3y = 5k + 12 \implies m = 12 \text { FALSE.}$

Thus, of the fifteen potential possibilities, only five are actual possibilities, namely V, VIII, IX, XI, and XII. Furthermore, each matches to a different possible value of m, and therefore we can reverse them. We can also see that if k = 0, only XI and XII result in a non-negative x so that V, VIII, and IX are impossible if n < 5. (That accounts for the lack of solutions if n = 1, 2, or 4.) Finally, if k = 1, V results in a negative x so that V is impossible if n < 10. (That accounts for the lack of a solutions if n = 7.)

So we have proved that there are solutions for x and y if n > 7 or if n = 3, 5, or 6. And the solutions can be found by the following algorithm, which is a fairly simple procedure.

$m = 0 \implies x = k \text { and } y = 0.$ XI

$m = 1 \implies x = k - 1 \text { and } y = 2.$ VIII

$m = 2 \implies x = k - 2 \text { and } y = 4.$ V

$m = 3 \implies x = k \text { and } y = 1.$ XII

$m = 4 \implies x = k - 1 \text { and } y = 3.$ IX

EDIT: It occurs to me that you might be interested in minimizing the number of packages even if one package is not completely filled. Calculate k and m as above. If m = 0, use k packages of size 5. If m = 1, 2, or 3, use k packages of 5 and and 1 package of size 3. If m = 4, use k + 1 packages of size 5.

9. Originally Posted by JeffM
I have a proof, but it is hardly elegant. But it turns into a fairly simple procedure, which is easily extended to product II.

$n \text { is a positive integer.}$

$\text {DEFINE: } k = \left \lfloor \dfrac{n}{5} \right \rfloor \text { and } m = n - 5k.$

$\therefore k \text { and } m \text { are integers, } n = 5k + m \text {, and } m = 1,\ 2,\ 3,\ \text { or } 4.$

$\text {DEFINE integers } x \text { and } y \text { such that (i) } 5x + 3y = n \text {, (ii) } x \ge 0 \le y \text {, and}$

$\text {(iii) if integers } a \text { and } b\ \exists \text { such that}$

$\text{(1) } 5a + 3b = n \text { and ( 2) } 0 \le b \ne y \text {, then } a + b > x + y.$

Note that x and y may not exist for every value of n.

We need three lemmas. LEMMA 1 states that if y exists, then y = 0, 1, 2, 3, or 4. Proof follows.

$\text {ASSUME non-negative integers } x \text { and } y \ \exists \implies 5x + 3y = n.$

$\text {ASSUME } y \ge 5.$

$\text {Let } a = x + 3 \text { and } b = y - 5 \implies a \text { and } b \text { are integers such that }$

$5a + 3b = 5x - 15 + 3y + 15 = 5x + 3y = n \text { and } 0 \le b \ne 5.$

$\text {By definition then, } a + b > x + y.$

$\text {BUT } a + b = (x + 3) + (y - 5) = (x + y) - 2 < x + y \text {, a CONTRADICTION.}$

$\therefore y \not \ge 5 \implies y = 0,\ 1,\ 2,\ 3, \text { or } 4\ \because \text { by definition } y \text { is an integer } \ge 0.$

LEMMA 2 states that if x exists, it does not exceed k. Proof follows.

$\text {ASSUME non-negative integers } x \text { and } y \ \exists \implies 5x + 3y = n.$

$\text {ASSUME } x \ge k + 1 \implies 5x + 3y \ge 5(k + 1) + 3y \implies n \ge 5k + 5 + 3y \implies$

$5k + m \ge 5k + 5 + 3y \implies 0 > m - 5 \ge 3y \implies y \not \ge 0\ \because \ m \le 4.$

$\text { BUT, by definition } y \ge 0 \text {, a CONTRADICTION.}$

$\therefore x \not \ge k + 1 \implies x < k + 1 \implies x \le k\ \because \text { by definition } x \text { is an integer.}$

LEMMA 3 states that if x exists, it is k - 2, k - 1, or k. Proof follows.

$\text {ASSUME non-negative integers } x \text { and } y \ \exists \implies 5x + 3y = n.$

$\text {ASSUME } x \le k - 3 \implies 5x + 3y \le 5(k - 3) + 3y \implies n \le 5k - 15 + 3y \implies$

$5k + m \le 5k - 15 + 3y \implies 15 \le m + 15 \le 3y \implies 5 \le y\ \because \ 0 \le m.$

$\text {BUT, by LEMMA 1, } y \le 4 \text {, a CONTRADICTION.}$

$\therefore x \not \le k - 3 \implies x > k - 3 \implies x \ge k - 2\ \because \text { by definition } x \text { is an integer.}$

$\text {By LEMMA 2, } x \le k \implies x = k - 2,\ k - 1, \text { or } k \ \because \text { by definition } x \text { is an integer.}$

Putting our lemmas together, there are exactly fifteen potential possibilities, and, by brute force, we can find x and y (if they exist) by examining all fifteen of them.

$\text {I: } x = k - 2 \text { and } y = 0 \implies n = 5x + 3y = 5k - 10 \implies m = -\ 10 \text { FALSE.}$

$\text {II: } x = k - 2 \text { and } y = 1 \implies n = 5x + 3y = 5k - 10 + 3 \implies m = -\ 7 \text { FALSE.}$

$\text {III: } x = k - 2 \text { and } y = 2 \implies n = 5x + 3y = 5k - 10 + 6 \implies m = -\ 4 \text { FALSE.}$

$\text {IV: } x = k - 2 \text { and } y = 3 \implies n = 5x + 3y = 5k - 10 + 9 \implies m = -\ 1 \text { FALSE.}$

$\text {V: } x = k - 2 \text { and } y = 4 \implies n = 5x + 3y = 5k - 10 + 12 \implies m = 2 \text { OK.}$

$\text {VI: } x = k - 1 \text { and } y = 0 \implies n = 5x + 3y = 5k - 5 \implies m = -\ 5 \text { FALSE.}$

$\text {VII: } x = k - 1 \text { and } y = 1 \implies n = 5x + 3y = 5k - 5 + 3 \implies m = -\ 2 \text { FALSE.}$

$\text {VIII: } x = k - 1 \text { and } y = 2 \implies n = 5x + 3y = 5k - 5 + 6 \implies m = 1 \text { OK.}$

$\text {IX: } x = k - 1 \text { and } y = 3 \implies n = 5x + 3y = 5k - 5 + 9 \implies m = 4 \text { OK.}$

$\text {X: } x = k - 1 \text { and } y = 4 \implies n = 5x + 3y = 5k - 5 + 12 \implies m = 7 \text { FALSE.}$

$\text {XI: } x = k \text { and } y = 0 \implies n = 5x + 3y = 5k \implies m = 0 \text { OK.}$

$\text {XII: } x = k \text { and } y = 1 \implies n = 5x + 3y = 5k + 3 \implies m = 3 \text { OK.}$

$\text {XIII: } x = k \text { and } y = 2 \implies n = 5x + 3y = 5k + 6 \implies m = 6 \text { FALSE.}$

$\text {XIV: } x = k \text { and } y = 3 \implies n = 5x + 3y = 5k + 9 \implies m = 9 \text { FALSE.}$

$\text {XV: } x = k \text { and } y = 4 \implies n = 5x + 3y = 5k + 12 \implies m = 12 \text { FALSE.}$

Thus, of the fifteen potential possibilities, only five are actual possibilities, namely V, VIII, IX, XI, and XII. Furthermore, each matches to a different possible value of m, and therefore we can reverse them. We can also see that if k = 0, only XI and XII result in a non-negative x so that V, VIII, and IX are impossible if n < 5. (That accounts for the lack of solutions if n = 1, 2, or 4.) Finally, if k = 1, V results in a negative x so that V is impossible if n < 10. (That accounts for the lack of a solutions if n = 7.)

So we have proved that there are solutions for x and y if n > 7 or if n = 3, 5, or 6. And the solutions can be found by the following algorithm, which is a fairly simple procedure.

$m = 0 \implies x = k \text { and } y = 0.$ XI

$m = 1 \implies x = k - 1 \text { and } y = 2.$ VIII

$m = 2 \implies x = k - 2 \text { and } y = 4.$ V

$m = 3 \implies x = k \text { and } y = 1.$ XII

$m = 4 \implies x = k - 1 \text { and } y = 3.$ IX

EDIT: It occurs to me that you might be interested in minimizing the number of packages even if one package is not completely filled. Calculate k and m as above. If m = 0, use k packages of size 5. If m = 1, 2, or 3, use k packages of 5 and and 1 package of size 3. If m = 4, use k + 1 packages of size 5.
However, this is well beyond anything somebody with knowledge only of "Arithmetic" would be able to do.

habla: What have you covered recently in class? What do you think your teacher is probably expecting you to do?

10. Originally Posted by stapel
However, this is well beyond anything somebody with knowledge only of "Arithmetic" would be able to do.

habla: What have you covered recently in class? What do you think your teacher is probably expecting you to do?

Stapel

This question does not appear to be a homework problem, but a question from someone who is trying to write a routine in JavaScript. In a previous post, I had given the procedure, but admitted I had not yet found a proof for it. I suspect there may be a simpler proof, and I agree that someone who knows only arithmetic is likely to find any proof of the procedure incomprehensible. Nevertheless, I would not give someone a procedure to use in real life without finding a proof that the procedure works.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•