假设存在带students[]
、ages[]
和subjectsFailed[]
的subjectsTaken[]
。假设每个学生的质量指数subjectsFailed[i]/subjectsTaken[i]
我需要选择学生,这样他们的年龄总和就最大化了,因为averageQualityIndex <= x
其中k是选定的学生。
在一般背包问题中,权重是独立的但是,在这种情况下,平均体重将取决于到目前为止选择的学生人数和他们各自的体重有没有办法我可以解决这个(最好的可能的解决方案)使用背包或有其他方式,我们解决这个问题(如果有,那么什么方法?).
最佳答案
您需要满足约束∑subjectsFailed[k]/∑subjectsTaken[k] <= x
。
两边乘以∑subjectsTaken[k]
,这就变成∑subjectsFailed[k] <= x.∑subjectsTaken[k]
。
重新排列我们发现∑(subjectsFailed[k]-x.subjectsTaken[k]) <= 0
或∑weights[k] <= 0
在weights[k] = subjectsFailed[k]-x.subjectsTaken[k]
处。
所以有了这个权重定义,它又变成了背包问题。
关于algorithm - 物品的重量取决于所选物品的背包问题,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/52486793/