Сегодня побывал на школьной олимпиаде г.Сургута, на ней мне встретилась интересная (даже может она и проста, но всё-таки). Условие напишу кратко (уж больно оно большое):
Есть N автомобилей, стоимость i-го автомобиля равняется a_i. Нужно найти максимальное количество автомобилей, потратив сумму не более S.
Хотелось бы услышать просто ход решения

Упорядочить цены по возрастанию, а потом идти по массиву и увеличивать переменную-счетчик машин, пока общая цена не превысит лимит..

Хмм)) Un, это пол проблемы
Вот к пример из задачи:
n=6 s=18
5 10 1 2 1 20.

Упорядочив массив получим последовательность (1, 1, 2, 5, 10, 20), при этом складывая получим...............
Так-так. Походу дела, что запутался на олимпиаде... Теперь я понимаю. Делал в принципе также, но почему-то у меня не уходила мысль о том, что можно купить больше не смотря на сам порядок.
Просто невнимательность
Но всё равно спасибо

> Нужно найти максимальное количество автомобилей, потратив сумму не более S.

Ответ N.
Или за поиск тоже платить надо?

TarasBer, почему именно N?))) мы ведь не можем купить все автомобил,и если у нас сумма денег меньше чем стоят автобили.

Зато мы можем найти все автомобили. В условии же сказано, что их надо только найти, а не купить.

Ну он в ускоренном личном варианте пересказывал, смысл понятен.. Самое обидное, когда так написано именно в задании, но ответ N точно не примут))

TarasBer, Поржал