Версия для печати
Убрать все задачи

---

Из заданных n предметов выбрать такие , чтобы их суммарный вес был менее 30 кг, а стоимость - наибольшей. Напечатать суммарную стоимость выбранных предметов. Точнее- заданы два массива положительных чисел А[1:n] и В[1:n]. Выбрать такие попарно различные числа i₁, i₂,... i_k, чтобы сумма

А[i₁] + A[i₂] +...+ A[i_k] < 30, а сумма

B[i₁] + B[i₂] +...+ B[i_k] = max была максимальной. Напечатать только величину max

Замечание. Можно предполагать , что предметы уже расположены в порядке возрастания или убывания веса А[i], стоимости В[i], цены В[i] / A[i] или какого-либо иного признака.

   Решение

Тема:    [ Теорема Птолемея ]

Сложность: 5 Классы: 9

Прислать комментарий

Условие

Четырехугольник ABCD вписанный. Докажите, что

Решение

Пусть S — площадь четырехугольника ABCD, R — радиус его описанной окружности. Тогда  S = S_ABC + S_ADC = AC(AB ^. BC + AD ^. DC)/4R (см. задачу 12.1). Аналогично  S = BD(AB ^. AD + BC ^. CD)/4R. Приравнивая эти выражения для S, получаем требуемое.

Источники и прецеденты использования