15.6 Упражнения¶
15.6.1 Вопросы для самопроверки¶
1. Всегда ли лучше брать самую крупную монету¶
Даны монеты номиналов [1, 7, 10] и целевая сумма 14.
- Запишите монеты, выбранные по правилу «каждый раз брать наибольший номинал, не превышающий оставшуюся сумму».
- Существует ли способ использовать меньше монет? Если да, приведите один пример; если нет, объясните почему.
- Доказывает ли результат, что эта жадная стратегия верна для любых номиналов монет?
Ответ
-
Жадный алгоритм последовательно выбирает
10 + 1 + 1 + 1 + 1, всего 5 монет. -
Способ с меньшим числом монет существует:
7 + 7, всего 2 монеты. -
Нет. Этот контрпример показывает, что для произвольных номиналов выбор наибольшей допустимой в данный момент монеты не всегда дает минимальное число монет; лучший на текущем шаге выбор может помешать получить более выгодную комбинацию в дальнейшем.
2. Какой предмет первым положить в рюкзак¶
В рюкзак вместимостью 4 килограмма можно положить следующие предметы. Разрешено брать только часть предмета, а полученная ценность пропорциональна взятому весу.
- предмет A: вес 4 килограмма, ценность 20;
- предмет B: вес 3 килограмма, ценность 18.
- Какова ценность одного килограмма каждого предмета? Какой предмет нужно брать первым?
- Заполните рюкзак по жадной стратегии для дробного рюкзака. Какова итоговая ценность?
- Если предметы можно делить, а рюкзак ограничен по общему весу, что следует сравнивать при выборе: общую ценность или ценность килограмма? Почему?
Ответ
-
Ценность килограмма A равна
20 ÷ 4 = 5, а килограмма B —18 ÷ 3 = 6, поэтому первым нужно взять B с большей удельной ценностью. -
Сначала берется весь предмет B: он занимает 3 килограмма и дает ценность 18. В рюкзаке остается место для 1 килограмма, поэтому затем берется 1 килограмм предмета A ценностью 5. Итоговая ценность равна
18 + 5 = 23. -
Рюкзак ограничен по общему весу, а предметы можно делить, поэтому нужно сравнивать ценность единицы веса. Хотя общая ценность A выше, ценность его килограмма ниже, чем у B. Если сначала полностью положить A, получится только ценность 20.
3. Как переместить два указателя на следующем шаге¶
Высоты вертикальных перегородок заданы массивом [1, 8, 6, 2, 5]. Для поиска наибольшей вместимости используются два указателя на концах массива.
Вместимость равна произведению высоты более короткой из двух перегородок на расстояние между их индексами.
- Сначала левый указатель находится по индексу 0, а правый — по индексу 4. Чему равна текущая вместимость? Какой указатель нужно переместить следующим?
- После одного перемещения, выбранного в вопросе 1, по каким индексам находятся указатели? Чему теперь равна вместимость? Какой указатель нужно переместить следующим?
- Для текущей пары перегородок можно переместить указатель как более короткой, так и более высокой перегородки. Какое перемещение еще может привести к большей вместимости и почему?
Ответ
-
Текущая вместимость равна
min(1, 5) × (4 - 0) = 4. Левая перегородка короче, поэтому нужно переместить левый указатель. -
После перемещения левый и правый указатели находятся по индексам 1 и 4. Текущая вместимость равна
min(8, 5) × (4 - 1) = 15. Теперь короче правая перегородка, поэтому следующим нужно переместить правый указатель. -
Большую вместимость еще может дать перемещение указателя более короткой перегородки. При перемещении более высокой перегородки расстояние между ними обязательно уменьшается, а высота контейнера по-прежнему ограничена оставшейся короткой перегородкой, поэтому вместимость может только остаться прежней или уменьшиться. Только перемещение короткой перегородки дает возможность встретить более высокую.
15.6.2 Задачи по программированию¶
1. Дробный рюкзак¶
Даны массивы одинаковой длины wgt и val, где wgt[i] > 0, val[i] >= 0, а вместимость рюкзака cap >= 0.
Каждый предмет имеется в одном экземпляре, но разрешено положить в рюкзак только его часть;
полученная ценность пропорциональна доле веса предмета, которую положили в рюкзак. Используйте жадный алгоритм
и верните максимальную суммарную ценность как вещественное число.
Подсказки
- Сначала вычислите ценность единицы веса каждого предмета как val[i] / wgt[i]; результат деления должен сохранять дробную часть
- Чем выше ценность единицы веса предмета, тем раньше его нужно класть в рюкзак
- Если оставшаяся вместимость меньше веса текущего предмета, возьмите такую его часть, которая точно заполнит рюкзак, и завершите работу