Жадный алгоритм в задаче о рюкзаке/Задачи/Тупая жадность - очень плохо

Стенина Мария, группа 974

Для доказательства необходимо предъявить для каждого B и k набор предметов, из которого жадный алгоритм выберет набор не менее чем в k раз дешевле оптимального. Предъявим такой набор. В наборе будет всего 2 предмета.

a_1 = 0.1B/k, c_1 = 0.5

a_2 = B, c_2 = k

В таком наборе относительная ценность первого предмета 5k/B, у второго просто k/B. Оба предмета одновременно в рюкзак не влезают, поэтому жадный алгоритм выберет первый предмет, как имеющий бОльшую относительную ценность. Но при этом, очевидно, в оптимальный набор должен входить второй предмет. Ценность оптимального набора равна k, ценность набора, выбранного жадным алгоритмом, равна 0.5, что меньше оптимальной стоимости больше, чем в k раз.