Internal states can profoundly alter the behavior of animals. A quantitative understanding of the behavioral changes upon metabolic challenges is key to a mechanistic dissection of how animals maintain nutritional homeostasis. We used an automated video tracking setup to characterize how amino acid and reproductive states interact to shape exploitation and exploration decisions taken by adult Drosophila melanogaster. We find that these two states have specific effects on the decisions to stop at and leave proteinaceous food patches. Furthermore, the internal nutrient state defines the exploration-exploitation trade-off: nutrient deprived flies focus on specific patches while satiated flies explore more globally. Finally, we show that olfaction mediates the efficient recognition of yeast as an appropriate protein source in mated females and that octopamine is specifically required to mediate homeostatic postmating responses without affecting internal nutrient sensing. Internal states therefore modulate specific aspects of exploitation and exploration to change nutrient selection.