Если я правильно понял условие задачи, то для входных тестов достоинства монет не изменяются, изменяется только общая сумма, которую требуется разложить. Матрица нужна только в случае, если нужно хранить разложения для подмножеств монет.
Мне кажется, вы всё усложняете. Рекуррентное соотношение должно быть проще:
C(i) — достоинство монеты i. C отсортирован в порядке возрастания.
С = {1,5,10,25,50} для нашего случая.
N (i, S) — количество разложений суммы денег S монетами достоинством от С(0) до C(i) включительно.
N(i,0) = 1 для любого i
N(i, k) = N( i-1, k — C(i) ) + N (i, k — C(i) ) (следует учитывать, что если индекс лежит за границами массива, значение равно 0)
Таким образом видим, что при каждой итерации используются только значения, полученные на текущей итерации и значения предыдущей итерации,
что позволяет нам хранить только две строки условной матрицы.
Вам следует ясней выражаться. Но вы правы. Ящики в оптимальной последовательности действительно будут расположены в порядке неубывания p+w (и в порядке неубывания p внутри групп с одинаковым p+w). Доказывается это действительно легко, по индукции. Ваше решение верное, и оно подтверждает утверждение, что эта задача является частным случаем задачи о рюкзаке.
В общем, вы молодец, поздравляю.
egork:
существует оптимальная башня в которой ящики идут сверху вниз в порядке возрастания p
не верна. Контрпример:
p 4 4 5 6 7
w 6 1 1 1 1
Я дал ссылку на статью в википедии. Посмотрите пункт «Задача о ранце с возможностью единичного выбора предмета». Примите стоимость предмета за 1. Добавляется дополнительное сравнение веса уже выбранных ящиков с P текущего ящика.
Автор, извините, но мне ваша статья не понравилась. Заходя под кат я надеялся увидеть или сложную, действительно «олимпиадную» задачку, или простую задачку, но с неординарным решением, в общем, хоть что-то. В результате получил простую задачу решённую очевидным способом «в лоб». Возможно, я не прав, но что тогда вы хотели донести до читателей?
Вы молодец! Если бы каждый разбирался в своей области так же хорошо, как Вы в своей, мир был бы намного лучше. Спасибо, что делитесь своими знаниями и опытом с сообществом.
Мои мысли по поводу того, почему Скайнет и иже с ним невозможны. Предположим, что создание ИИ возможно. В таком случае, пока роботы будут глупее нас — они не будут представлять опасности для человечества. Если вдруг они станут умнее нас — они не станут пытаться воевать с человеками и пытаться их уничтожить. Почему? Да потому что война ведётся ради захвата ресурсов и использует инстинкт самосохранения. Не будь этого инстинкта, проигравшая сторона самоуничтожалась, не оставляя победителю ничего, практически лишая войну смысла. Роботы по сути бессмертны, основной ресурс для них — энергия, которой предостаточно вокруг и без людей. Из возможных причин воевать остаётся только бессмысленная жестокость, которой не должно быть у роботов, превзошедших людей по уровню интеллекта.
Более того, в тексте явно указано, что у девайса есть клавиатура (по крайней мере, цифровая), также девайс, похоже, ориентирован на чтение текста, а не на мультимедиа. Это делает его больше всего похожим на E-Ink читалки. Жаль, что автор предпочёл логике «модные тренды».
C(i) — достоинство монеты i. C отсортирован в порядке возрастания.
С = {1,5,10,25,50} для нашего случая.
N (i, S) — количество разложений суммы денег S монетами достоинством от С(0) до C(i) включительно.
N(i,0) = 1 для любого i
N(i, k) = N( i-1, k — C(i) ) + N (i, k — C(i) ) (следует учитывать, что если индекс лежит за границами массива, значение равно 0)
Таким образом видим, что при каждой итерации используются только значения, полученные на текущей итерации и значения предыдущей итерации,
что позволяет нам хранить только две строки условной матрицы.
Само собой.
Вам следует ясней выражаться. Но вы правы. Ящики в оптимальной последовательности действительно будут расположены в порядке неубывания p+w (и в порядке неубывания p внутри групп с одинаковым p+w). Доказывается это действительно легко, по индукции. Ваше решение верное, и оно подтверждает утверждение, что эта задача является частным случаем задачи о рюкзаке.
В общем, вы молодец, поздравляю.
не верна. Контрпример:
Я дал ссылку на статью в википедии. Посмотрите пункт «Задача о ранце с возможностью единичного выбора предмета». Примите стоимость предмета за 1. Добавляется дополнительное сравнение веса уже выбранных ящиков с P текущего ящика.