У Алисы есть 21 рубль. Она пришла в магазин, в котором продавались значки семи различных цветов стоимостью 4, 6, 7, 8, 9, 10, 11 рублей. Сколькими способами она может купить наибольшее количество значков разных цветов? Алиса не обязана потратить все деньги.
Значки разных цветов, поэтому каждую цену можно взять не более одного раза.
Значит, наибольшее количество значков —
Набор с самым дешёвым значком за
, , , , — способов; , , — способа ( не подходит); — способ ( не подходит); не подходит.
Итого с четырёхрублёвым значком:
Наборы без значка за
— подходит, — нет.
Это
Сначала находим максимальное число значков по самым дешёвым, затем перебираем все наборы такого размера с суммой не больше
