Nano Hash - криптовалюты, майнинг, программирование

Не более k соседних единиц (максимальное значение ограничено соседями)

В моем курсе по алгоритмам в книге есть вопрос следующего содержания: «Вам дан массив a[1..n] положительных чисел и целое число k. Вы должны создать массив b[1..n] , так что: для каждого j, b[j] равно 1 или 0. Массив b имеет соседние единицы не более K раз. Сумма (a[j]*b[j]) для 1 ‹= j ‹= n максимальна ." Например, для массива [10, 100, 300, 400, 50, 4500, 200, 30, 90] и k = 2 массив b может быть = [1, 0, 1, 1, 0, 1, 1, 0 , 1], что максимизирует сумму до 5500.

В решении используется динамическое программирование. При обсуждении этого с некоторыми друзьями они сказали, что рекуррентное соотношение имеет форму M (i, j) = max (M (i-2, j) + a [i], M (i-1, j -1) + а[и])

может кто-нибудь объяснить, почему так? или если у них другая форма решения такой задачи. Я нахожу динамическое программирование немного сложным для понимания. Спасибо.

arrays dynamic algorithm dynamic-programming
13.06.2015

Ответы:


1

M[i, j] — максимальная сумма от 1 до i, где j соседние единицы

M[i,j] может быть вычислено как максимальное из 3 ситуаций:

b[i]=0  =>  S=M[i-1, j]   // a[i] not added to sum, b[1..i-1] has same number of adjacent 1s (j) as b[1..i] because b[i] is zero

b[i]=1 and b[i-1]=0  => S=M[i-2, j]+a[i]   // a[i] added to sum, b[1..i-2] has same number of adjacencent 1s, because b[i-1] is zero

b[i]=1 and b[i-1]=1  => S=M[i-1, j-1]+a[i]   // a[i] added to sum, since b[i] and b[i-1] are both 1, they count as adjacent 1s, so b[1..i-1] contains only j-1 adjacent 1s

Рекурсивное правило - это максимальная из 3 сумм выше. Конечным условием является M[1, j]=a[1], потому что b[1..1] имеет только один элемент b[1]=1 и не имеет смежных единиц.

Нам нужен ответ M[n, k].

Сложность O(nk).

13.06.2015
  • ВНИМАНИЕ !!!! Ответ Хуана Лопеса выше неверен - попробуйте запустить printsolve([100,100,1,100],1), и вы получите [0, 1, 0, 1] вместо [1,1,0,1] . Почему вы публикуете неправильный ответ ПОСЛЕ того, как я уже разместил правильный ответ? Желательно сначала прочитать существующие ответы. P.S. заглавные буквы предназначены для типов и классов, а не для переменных! это общепринятое соглашение. 14.06.2015
  • Нет. solve([100,100,1,100],1) означает, что не может быть более 1 смежных единиц. Итак, [1, 1, 0, 1] не является правильным ответом. И я разместил свой ответ именно потому, что считаю ваш ответ неправильным. Кроме того, не беспокойте других авторов только потому, что вы написали первым. 14.06.2015
  • printsolve([10, 100, 300, 400, 50, 4500, 200, 30, 90], 2) выводит [1, 0, 1, 1, 0, 1, 1, 0, 1], который содержит две соседние пары !!! аналогично [1,1,0,1] имеет ровно 1 соседнюю пару, что я и просил. 14.06.2015
  • Я думаю, что это не то, что вопрос действительно задает. Нам нужно больше примеров OP, чтобы быть уверенным. Или пусть решает ОП. Но нельзя редактировать чужой ответ, если вы с ним не согласны. Обратите внимание, что я даже не минусовал ваш ответ. 14.06.2015
  • ну, ваш собственный код возвращает [1,0,1,1,0,1,1,0,1] для исходного примера, что правильно, поскольку он содержит две соседние пары последовательных единиц. Просто ваш код дает неверный ответ для arr=[100,100,1,100] и k=2, потому что он игнорирует рекурсивный случай M[i-2, j]+a[i]. 14.06.2015
  • Мой код возвращает [1,0,1,1,0,1,1,0,1], потому что он содержит не более 2 смежных 1, а не потому, что он содержит 2 экземпляра соседних 1. 14.06.2015
  • я вижу, так что вы обрабатываете слово смежное со средним последовательным, поэтому для исходного входного массива и k = 3 ваш код возвращает [0, 1, 1, 1, 0, 1, 1, 0, 1], что правильно под вашей (сомнительной) трактовкой вопроса. 14.06.2015
  • Просто чтобы прояснить ситуацию, gen-y-s прав насчет смежности. Его не волнует последовательность. А что касается рекуррентного отношения, когда вы говорите a[i] = 0, вы имеете в виду массив b[i]? 16.06.2015
  • @Athoug хорошо, удаляю мой ответ. Пожалуйста, отметьте этот ответ как правильный, если он отвечает на ваш вопрос. 17.06.2015
  • сложность O(NK) . Что ж, мы можем сделать это за O(N), используя F(N)=max(Сумма от N до N-K + F(N-K-1),F(N-1)). Серьезно, кто голосует за это? 02.07.2015
    • Новые материалы
    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..