1 Тема от ploskov Отредактировано ploskov (2013-01-11 12:38:04)

  • ploskov
  • Участник
  • Неактивен
  • Зарегистрирован: 2013-01-11
  • Сообщений: 1

Тема: Ранец (задача о рюкзаке/ранце)

Доброго всем дня.
  Прошу помочь разобраться с алгоритмом, описываемом здесь: http://habrahabr.ru/post/93698/
  А точнее, помогите понять задачу для одного конкретного случая: собрать в рюкзак камешки, если каждый камешек в единственном числе. В общем, стоимость даже не важна, важна достижимость результата - то, что рюкзак будет полностью заполнен (ну, либо заполнение недостижимо). Желательно, в числах. Просто привести пример, как будет работать алгоритм (пример прохода какого-либо показательного случая алгоритмом). Код попрошу не приводить. smile
  Заранее благодарен.
Если автор решения будет не против, затем помещу его алгоритм в шапку, чтобы было проще искать позже.

2 Ответ от grom4ik

  • grom4ik
  • Участник
  • Неактивен
  • Зарегистрирован: 2013-11-25
  • Сообщений: 1

Re: Ранец (задача о рюкзаке/ранце)

Добрый день!Если хотите могу рассказать алгоритм и дать код но не этом форуме а в частной беседе(бесплатно).пишите на o.a.gromyak@gmail.com

3 Ответ от MBo Отредактировано MBo (2013-11-29 09:06:21)

  • MBo
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-10-05
  • Сообщений: 52

Re: Ранец (задача о рюкзаке/ранце)

>В общем, стоимость даже не важна
Тогда это задача о наборе суммы. Пример: есть по одной монете 1, 3 и 5 копеек. Определить,какие суммы можно набрать. Используем восходящее ДП.
Делаем массив S[] длиной MAXSUM + 1, нулевую ячейку инициализируем единицей, остальные нулями (можно логический тип использовать).
Для каждого числа M[j] пробегаем по массиву S. Встретили ненулевую ячейку с индексом k - пишем единицу в ячейку S[k + M[j]]
Состояние массива после обработки для приведенных данных:
1 1 0 1 1 1 1 0 1 1