algorithm - 扭曲背包问题(无界斐波那契约束)

Question

在我的两次招聘挑战中(在 HackerEarth 上)，我遇到了以下问题。该问题无法在线获得，因此这里是我内存中的问题陈述:

给定一个背包 M重量和n元素，每个元素的重量都是正数 w和正值v (作为数组 weight[] 和 val[] 给出)。每个项目都可以无限次使用。但是如果你拿了一个项目 x次数，那么所有其他项目(如果被拿走)都必须被拿走x次数。
这里x是一个小于 100 的斐波那契数。
当背包的总重量为<= M时，求出你能拥有的最大值.

约束:
n <= 20
(M, 权重, 值)<=1e9

示例测试用例:

n=2, M = 125
权重=[50, 25]
值 =[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同时保持到目前为止获得的最大 val 的计数。在 2^n 之后迭代，即使我得到了答案，但它只通过了 15 个测试用例中的 3 个，其余的都获得了 TLEd。

Answer 1

我认为一个小的优化就能通过所有测试用例。为 x 预先计算最接近的较小斐波那契数。现在在生成所有子集 sum 之后，将 m 除以 sum 。找到最近的较小斐波那契数 ( m/sum)。乘以总和。所以整体时间复杂度为O(2^n)。