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?



Integer programming for bin covering problem
This is equivalent to a special case of the [0-1 knapsack problem](https://en.wikipedia.org/wiki/Knapsack_problem), and the [greedy heuristic](https://en.wikipedia.org/wiki/Knapsack_problem#Greedy_approximation_algorithm) suggested by @TonyHuynh is well known but not necessarily optimal for the general case, which you can solve exactly with [dynamic programming](https://en.wikipedia.org/wiki/Knapsack_problem#0-1_knapsack_problem).


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


