Я столкнулся со следующей проблемой во время двух из моих трудоустройств (на HackerEarth). Этот вопрос недоступен в Интернете, поэтому вот формулировка проблемы, насколько мне известно:
Учитывая рюкзак с M весом и n элементами, каждый с положительным весом w и положительным значением v (задается как массив weight[] и val[]). Каждый элемент доступен бесконечное количество раз чтобы быть взятым. Но если вы берете предмет x количество раз, то все остальные предметы (если они взяты) должны быть взяты x количество раз.
Здесь x - число Фибоначчи меньше 100.
Найдите максимальное значение, которое вы можете иметь, пока общий вес рюкзака составляет <= M.
Ограничения:
n <= 20 <br>
(М, веса, значения) <= 1e9 </p>
Образец теста:
n = 2, M = 125
вес = [50, 25]
val = [100, 51]
для x = 1: максимальное значение равно 100 + 51 = 151
для x = 2: максимальное значение равно 2 * 100 = 200
для x = 3: максимальное значение равно 3 * 51 = 153
для x = 5: максимальное значение 5 * 51 = 255
для остальных значений x: max val будет 0
Может кто-нибудь подсказать, как к нему подойти?
Вот что я сделал:
Сгенерировал все возможные подмножества элементов (используя битовую маску), и для каждого поднабора я продолжал умножать его вес на x = 1,2,3,5..., пока вес не превысит M, сохраняя при этом счет максимального значения, полученного до сих пор. После 2^n итерации, хотя у меня был свой ответ, но он прошел только 3 из 15 тестовых случаев и получил TLEd для остальных.