0

During Software designing our team come across the following problem: we have linear Diophantine equation with n variables with each variable have positive permissible range or allowed range.

a1x1+a2x2+....+anxn = b
known parameters:
a1,a2,...,an and b
unknown parameter x1,x2,....,xn
but we know that 
x1 belongs to range [l1,r1]
x2 belongs to range [l2,r2]
.
.
.
xn belongs to range [ln,rn]
0<li<ri
ai>0
b>0

and we need to find values of all xi in above equation(may be float or integer). I have come across lot of solution online one of them CP-algorithm and another one is reduce problem Coin change problem of DP. But I am thinking there must be better algorithm to this problem.

Umang Patel
  • 19
  • 5
  • If the `a_i` are all positive, then reducing to the coin change problem seems like the correct approach. – user3386109 Oct 17 '20 at 06:58
  • you can even use fitting ... btw is this on integers or floats? are the ranges positive or non negative only? what are the limits of `m=max(r(i)-l(i))` and `n` ... as brute force solution is `O(m^n)` ... fitting like [this](https://stackoverflow.com/q/36163846/2521214) might convert this into `O((log(m))^n)` – Spektre Oct 17 '20 at 08:06
  • Thanks guys for comment this really help me to solve the problem – Umang Patel Oct 18 '20 at 09:04

0 Answers0