Knapsack problem with item's weight depending on items selected

Question

Suppose there are students[] with ages[], subjectsFailed[] and subjectsTaken[]. Suppose Quality Index for each student is subjectsFailed[i]/subjectsTaken[i]. I need to select students so that sum of their ages is maxed given that averageQualityIndex <= x where

averageQualityIndex = ∑subjectsFailed[k]/∑subjectsTaken[k] where k are the students selected.

In normal knapsack problems, the weights are independent. But, in this case, the average weight will depend on the number of students selected till now and their respective weights. Is there a way I can solve this (best possible solution) using knapsack or there is some other way in which we solve this problem (if yes, then what method?).

Answer 1

You want to satisfy the constraint ∑subjectsFailed[k]/∑subjectsTaken[k] <= x.

Multiplying both sides by ∑subjectsTaken[k], this becomes ∑subjectsFailed[k] <= x.∑subjectsTaken[k].

Rearranging we find ∑(subjectsFailed[k]-x.subjectsTaken[k]) <= 0 or ∑weights[k] <= 0 where weights[k] = subjectsFailed[k]-x.subjectsTaken[k].

So with this definition of weights it becomes a knapsack problem again.