物品重量取决于所选物品的背包问题
Knapsack problem with item's weight depending on items selected
假设有 students[] 和 ages[]、subjectsFailed[] 和 subjectsTaken[]。假设每个学生的质量指数为 subjectsFailed[i]/subjectsTaken[i]。我需要 select 学生，以便他们的年龄总和最大，因为 averageQualityIndex <= x where
averageQualityIndex = ∑subjectsFailed[k]/∑subjectsTaken[k] 其中 k 是学生 selected.
在正常的背包问题中，权重是独立的。但是，在这种情况下，平均权重将取决于 select 到目前为止的学生人数以及他们各自的权重。有没有一种方法可以使用背包解决这个问题（最佳解决方案），或者有其他方法可以解决这个问题（如果是，那么什么方法？）。
您想满足约束条件∑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].
所以有了这个权重的定义，它又变成了一个背包问题。
假设有 students[] 和 ages[]、subjectsFailed[] 和 subjectsTaken[]。假设每个学生的质量指数为 subjectsFailed[i]/subjectsTaken[i]。我需要 select 学生，以便他们的年龄总和最大，因为 averageQualityIndex <= x where
averageQualityIndex = ∑subjectsFailed[k]/∑subjectsTaken[k] 其中 k 是学生 selected.
在正常的背包问题中，权重是独立的。但是，在这种情况下，平均权重将取决于 select 到目前为止的学生人数以及他们各自的权重。有没有一种方法可以使用背包解决这个问题（最佳解决方案），或者有其他方法可以解决这个问题（如果是，那么什么方法？）。
您想满足约束条件∑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].
所以有了这个权重的定义，它又变成了一个背包问题。