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).
What slicker techniques are there for solving this minimization problem?
Is there existing software that will solve this problem?
Responding to some comments...
CMichael (1): I get to make the decision at the end of the month when I am paying my bill. Instead of paying the entire bill, I can use points to pay off some purchases and then pay off the remaining bill. I want the remaining bill to be minimized.
CMichael (2): If I want to use points towards a purchase, I have to cover all of that purchase with points. If my purchases is \$100 or 10,000 points, I can either spend the \$100 or the 10,000 points, but \$50 and 5000 points would not be allowed.