Цитата(poor_yorik @ 27.6.2005, 22:05)

ДАААААА я решил єту задачу Динпрогом.

Если я правильно понял код (согласно которому решается некоторая другая, похожая на эту, задача ), то решение жадное... а раз так, то вопрос открыт, почему это правильно??
и интересно, как ты определил, что она(твоя прога) работает правильно???

Это сообщение отредактировал(а) yaja - 28.6.2005, 14:30

Смотри yaja!
Во первых, я оттестировал свою прогу на все 100. И Для всех мерзких случаев, которые сам придумал.
Ты не будешь спорить, что если бы у нас была одна доска, то задача была бы почти-что такая же как задача про рюкзак. В принципе она больше похожа на задачу про камни, если ты знаешь, но с одним большим отличием: у нас количество маленьких досок одного типа, на которые мы можем рубить большие НЕОГРАНИЧЕНО. Я это сам вначале не заметил.
То есть если, у нас две большие доски длинной 5 и 7. И набор длин 2, 3, 4. То оптимальное решение [2, 3] и [3, 4]. Ответ остаток 0.
Так вот у меня задача динпрогом находит ответ (остаток) для всех досок длинами от 0 до Lmax, где Lmax - длина наибольшей из даных досок. А потом она уже сумирует остатки нужных мне досок так и получает сумарный результат.
Советую тебе посмотреть что-нибудь по ДинПрогу, а особенно о задаче про рюкзак.