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.