Ubuntu 16.4 LTS cannot find openjdk-8-jdk
Solution 1:
Did you do sudo apt-get update recently? If not, do that, then try again.
The 404 error is that it's hunting a specific version of the package that is not available on the repos anymore, and this usually happens when your repository 'state' information is out of date. Usually a call to sudo apt-get update will fix that problem, and then you can retry the sudo apt-get install command you were trying to run again.