Жадный алгоритм в задаче о рюкзаке/Задачи/Тупая жадность - очень плохо — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
|||
| Строка 1: | Строка 1: | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | [[ | + | === Стенина Мария, группа 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 раз. | ||
Версия 12:28, 19 сентября 2014
Стенина Мария, группа 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 раз.