Alex has some (say, n) marbles (small glass balls) and he has going to buy some boxes to store them. The boxes are of two types:

Type 1: each box costs c1 Taka and can hold exactly n1 marbles

Type 2: each box costs c2 Taka and can hold exactly n2 marbles

He wants each of the used boxes to be filled to its capacity and also to minimize the total cost of buying them. Since he finds it difficult to figure out how to distribute his marbles among the boxes he seeks his friends' help. It is worthy of mention that the value of n,c1,n1,c2 and n2 are given.

His one friend solved this problem using extended euclidian algorithm and found out two values everytime .Thus his result for the input.

1.n=43,c1=1,n1=3,c2=2,n2=4 the result will be 13 1

2.n=40,c1=5,n1=9,c2=5,n2=12,the result will be "no valid values".

Though I understand extended euclidian algorithm I can not catch how he solved this problem. Can anyone tell me how his friend sovled it using extended euclidian algorithm. Since I'm a novice learner of extended euclidian algorithm I need better explanation.


Here are some ideas to get you started.

  1. A number $n$ cannot be represented as a linear combination of $n_1,n_2$ unless $(n_1,n_2) \mid n$, since all linear combinations of $n_1,n_2$ are multiples of $(n_1,n_2)$.

  2. The extended Euclidean algorithm gives you values $a_1,a_2$ such that $a_1n_1+a_2n_2 = (n_1,n_2)$, and in particular $$\frac{n}{(n_1,n_2)} a_1 n_1 + \frac{n}{(n_1,n_2)} a_2 n_2 = n.$$

  3. If $n = b_1 n_1 + b_2 n_2$ then all other representations are of the form $$n = \left(b_1 + \frac{n_2}{(n_1,n_2)} t \right) n_1 + \left(b_2 - \frac{n_1}{(n_1,n_2)} t \right) n_2.$$

Try to use these ideas to solve the problem on your own.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.