In general, "exact change" policies are legal.
The Coinage Act of 1965, specifically Section 31 U.S.C. 5103, entitled "Legal tender," ... states: "United States coins and currency (including Federal reserve notes and circulating notes of Federal reserve banks and national banks) are legal tender for all debts, public charges, taxes, and dues."
This statute means that all United States money as identified above are a valid and legal offer of payment for debts when tendered to a creditor. There is, however, no Federal statute mandating that a private business, a person or an organization must accept currency or coins as for payment for goods and/or services. Private businesses are free to develop their own policies on whether or not to accept cash unless there is a State law which says otherwise. For example, a bus line may prohibit payment of fares in pennies or dollar bills. In addition, movie theaters, convenience stores and gas stations may refuse to accept large denomination currency (usually notes above $20) as a matter of policy.
But in practice doesn't this mean that "exact change" policies can only be enforced when payment is required before a good or service is provided? Because I can incur a debt in most commercial situations. E.g.:
I drive into a parking garage that lists rates on a sign that also warns, "Exact change required." Later when I go to leave I am asked for exact change at the exit. I say, "Well, I don't have exact change, but I do owe you money for parking here. Federal law says I can satisfy this debt with legal tender. So start counting the pennies, or just let me out!"
I go into a store that says, "No bills larger than $20 accepted." While shopping I drink a soda and eat a few snacks. I go to check out and all I have is a $100 bill. Once again I say, "All I have is this $100 bill. I am in debt to you for the food I've already consumed, and this bill is legal tender for satisfaction of that debt. Either make change or thank you for the free snack."
I get in a taxi, enjoy a meal in a restaurant, etc. All of these are paid after the service has been consumed. Are they not then debts that must be discharged if I offer legal tender?