0
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Tony Huynh
    Commented Jul 19, 2021 at 2:07
  • $\begingroup$ 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. $\endgroup$
    – Yorknight
    Commented Jul 19, 2021 at 2:23
  • 1
    $\begingroup$ 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! $\endgroup$
    – Will Sawin
    Commented Jul 26, 2021 at 21:34

1 Answer 1

Reset to default
1
$\begingroup$

This is equivalent to a special case of the 0-1 knapsack problem, and the greedy heuristic suggested by @TonyHuynh is well known but not necessarily optimal for the general case, which you can solve exactly with dynamic programming.

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you. This is very helpful. $\endgroup$
    – Yorknight
    Commented Jul 19, 2021 at 2:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .