I tried to install Caffe through the link https://caffe.berkeleyvision.org/install_apt.html and I got the error
E: Unable to locate package caffe-cuda.
Can anyone suggest a solution?
According to the link in your question everything including caffe itself is packaged in 17.04 and higher versions, but you are currently using Ubuntu 16.04 which does not contain these packages in its default repositories.
caffe-cuda is not available from the default Ubuntu 16.04 repositories. Ubuntu 16.04 can be upgraded directly to Ubuntu 18.04 which is the next LTS release after 16.04. To install caffe-cuda in Ubuntu 18.04 and later open the terminal and type:
sudo apt install caffe-cuda
For information about installing other caffe packages in Ubuntu 16.04 see this answer.