How to determine what battery to use?
The LM317 is a linear regulator, which means the output voltage is always lower than the input voltage. As the 317 is quite old, it's at least 3 V lower than the input voltage.

The diagrams say '3-40 V' on the input. That's the rating for the LM317s, not the ratings for the circuits as shown. The 12 V circuit should say '15-40 V' on the input, the 5 V circuit '8-40 V'. 

Your comment about using two A batteries suggests you were hoping that these were boost converters. It also suggests you are a long way from designing anything starting from components.

In which case, although knowing nothing about your loads, you may want to consider this as a starting point. Use a 5 V 'powerbank' as your single 'battery', and the supply to your 5 V load. They are easy to charge (usually from USB), have constant voltage out, and they are protected from all sorts of over- and under- abuse. Buy a 5 V to 12 V boost converter module from one of the online retailers, and use it to power your 12 V load.

If this isn't suitable, then we need to know more about your loads, application, and other constraints.