I was trying to solve a problem where I want to choose which items to choose where each item has a number b_i associated with it and a reward r_i associated with it. I need to choose items that maximize my reward but the sum of the b_i's need to be less than MAX. My initial thought was to use linear programming (let me know if this is not the correct route).
I think I came up with the correct objective function and constraints but then I realized I would need an additional constraint to make sure the choice of an item x_i was an integer, in particular, 0 or 1. But I read that integer programming is not guaranteed to be efficient like linear programming even if it's binary.
But, my main confusion is that the example used to show the efficiency is assigning 70 jobs to 70 men which requires finding a value of 0 or 1 for each pairing of man and job, which is integer programming. Why is this efficient- is this different from my program? How can I know whether or not my program will be efficient like this integer program when integer programs are supposed to be NP-hard?
EDIT: My question is: To settle an account, I will deposit the user’s entire balance to their bank account. I can only settle up to S dollars at a time. For each account I settle, I receive a rebate which is a fixed dollar amount. How can I maximize the rebate while making sure I don't settle more than S dollars? For each account, I'm given the balance and the rebate amount. There may be many accounts (about 100 I think).
EDIT2
Here's an example:
MAX = 50
User1: balance = 15, rebate = 10
User2: balance = 25, rebate = 15
User3: balance = 40, rebate = 20
In this case I would choose User1 and User2 to maximize my rebate without having a balance greater than MAX. My rebate would be 10+15=25 and the balance would be 15+25=40.
The way I was trying to solve this was by using linear programming but now I'm not sure if that's guaranteed to be efficient in my case (there might be 100 or so users).
This is what my linear programming objective function was:
f(x1, x2, ... xn) = r1*x1+r2*x2+...+rn*xn
These were my constraints:
x1*b1+x2*b2+...xn*bn <= MAX
xi is in {0, 1} (not sure how to represent this constraint in the matrix but the example I keep seeing in introductions to Linear Programming is the "70 men, 70 jobs" problem and it has the same binary restriction, yet somehow it's guaranteed to be efficient)
