arrays - 最大总和小于限制

Question

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

我的尝试——

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

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

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

请提出解决此问题的正确算法。

Answer 1

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

Answer 2

这是一个众所周知的 NP 难题，因此如果您的解决方案是指数级的，请不要担心。