Жадность по удельной ценности: где она оптимальна, а где нет
Рюкзак вместимости 10. Три предмета:
A: вес 6, ценность 12 (ценность на единицу веса 2.0)
B: вес 5, ценность 9 (1.8)
C: вес 5, ценность 9 (1.8)
Жадный алгоритм сортирует предметы по убыванию отношения ценность/вес и берёт подряд те, что помещаются целиком.
Что верно про такую стратегию?
- Жадность по отношению оптимальна и для целого рюкзака: здесь она наберёт 21, взяв A и C
- Для дробного рюкзака она оптимальна, для целого — нет: здесь она даст 12, а оптимум 18
- Здесь она даёт 18: после A в рюкзаке остаются 4 единицы вместимости, их добирают частью B
- Сортировка по убыванию отношения всегда проигрывает сортировке по убыванию ценности предмета