# Allocating credit card points

I’m interested in the idea behind this in general, so I thought this would be the best place to post, though I have a practical and semi-urgent need of allocating the points on my credit card towards purchases.

Each purchase I make can be paid for in points. However, it goes by purchase, not by my total bill. Therefore, I can wind up with points left, but too few to be able to put them towards a purchase. Further, points don’t have the same value for each purchase. One purchase may regard a point as a cent, while another may regard a point as 0.9 cents.

My goal is to have as little left on my bill after I use points. Certainly I can do this by brute force and try out every combination of purchases to see which results in the lowest remaining bill, but that lacks elegance and seems like it would be quite slow (dealing with factorials).

My Questions

1. What slicker techniques are there for solving this minimization problem?

2. Is there existing software that will solve this problem?

Thanks!

EDIT