Я пытаюсь решить модифицированную версию задачи о ранце, используя алгоритм восхождения на холм, но не могу найти хорошую функцию оценки.В этой версии задачи о рюкзаке сумма весов всех объектов в решении должна быть равна (не <=) емкости рюкзака, а сумма их стоимости должна быть максимальной. </p>
Я пробовалнесколько функций оценки, но ни одна из них не сработала:
- Я пытался минимизировать выражение
__abs(sum_of_weights_in_solution - knapsack's capacity)__.Очевидно, что это не сработало, потому что это выражение не учитывает стоимость объекта, но, по крайней мере, оно предоставляет решение, которое заполняет рюкзак
- Я пытался минимизировать это выражение:
__abs(sum_of_weights_in_solution - knapsack's capacity) - sum_of_costs_in_solution__.Этот вариант лучше, но, тем не менее, он не всегда находит оптимальное решение даже после 10 ^ 6 итераций в рюкзаке с 10 объектами, и я думаю, что это потому, что я не могу реально обработать случаи, когда сумма весов объектов равна> чем вместимость ранца