ЭВМ/ Переформулировка задачи упаковки

01.10.2012

Можно дать такую задачку на школьную олимпиаду по информатике.

«Кате и Пете на новоселье подарили карту Икеа на 5000 рублей. Они накупили барахла на 10000 рублей. На кассе выяснилось, что за раз можно расплатиться либо картой, либо наличными, но не одновременно. Поэтому им нужно разделить товары на две части так, чтобы первая часть была максимально близка к 5000, но не превышала эту сумму. Тогда они потратят свой подарок максимально эффективно. Помогите Кате и Пете решить эту задачу.»

Кто не узнал, это задача об упаковке, входит в класс сложности NP, то есть не решаемых эффективно за приемлемое время. Маленькие дети узнать ее не должны (ну, самые умные конечно в курсе, но большинство наверное нет), и на больших тестовых данных быстро убедятся, что перебор не работает. После чего можно наблюдать, кто какие эвристические алгоритмы придумает.