I was having the same issue and tried all of the solutions on this page but none of them did the trick.
What finally worked was adding the universe
repo to my repo list. To do that run the following command
sudo add-apt-repository universe
After running the above command I was able to run
sudo apt install openjdk-8-jre
without an issue and the package was installed.
Hope this helps someone.