arrays - 小于限制的最大总和

Question

我一直在努力解决问题 http://www.spoj.pl/problems/RPLB/但无法提出算法。

我的尝试-

1. 将输入分成两个数组，一个是奇数索引处的值，另一个是偶数索引处的值。之后，对两个数组进行排序并将数字相加，直到总和小于限制。我很快就通过一些测试用例找到了这个缺陷。

2. 我将输入存储在一个数组中，并且每次我尝试添加最大的剩余数字，条件是它不与任何已添加的数字相邻，但这个算法也被证明是错误的。

现在，通过尝试所有可能的组合，我能想到的唯一解决方案是指数级的:(

请建议解决此问题的正确算法是什么。

Answer 1

这是带有附加约束的 KNAPSACK 问题(您不能选择两个相邻的灌木丛)，并且附加约束不会使其变得更容易或更难。由于它与 KNAPSACK 一样难，即 NP-complete，因此除了蛮力搜索(可以优化但无论如何仍将保持指数/超多项式)之外，基本上没有其他事情要做。