# Integer programming for bin covering problem

I encounter an integer programming problem like this:

Suppose a student needs to take exams in n courses {math, physics, literature, etc}. To pass the exam in course i, the student needs to spend an amount of effort e_i on course i. The student can graduate if she/he passes 60% of the n courses (courses have different weights). The objective is to allocate her/his efforts to different courses such that the student can graduate with the minimal amount of efforts spent on courses.

I think this problem is similar to bin covering problem when there is only one bin. The formulation is simple. Use x_i\in{0,1} to denote whether the student allocates effort to course i. Let w_i denote the weight of course i in calculating the final score.

Min \sum x_i e_i

s.t. \sum x_i w_i >= 60% * n (or some other predetermined threshold)

My question is, is there a simple heuristic solution for this problem?

• Can't you solve the problem exactly by sorting the efforts from smallest to largest and to spend effort on the easiest 60% of classes? Jul 19 '21 at 2:07
• Yes, you are right. This should be the optimal strategy if the courses have the same weight. But if the courses have different weights, I doubt. My original question is not clear, I will update it. Jul 19 '21 at 2:23
• People often worry that students will try to use Q&A sites like mathoverflow to pass their courses with the minimal amount of effort, but usually not in this way! Jul 26 '21 at 21:34

In your special case, where each $$x_i$$ has the same constraint coefficient, greedy is optimal.