arrays - 制限未満の最大合計

Question

私は問題http://www.spoj.pl/problems/RPLB/を解決しようとしていますが、アルゴを思い付くことができません。

私の試み-

1. 入力を2つの配列に分割します。1つは奇数インデックスの値で、もう1つは偶数インデックスの値です。その後、両方の配列を並べ替え、合計が制限より少なくなるまで数値を加算します。私はすぐにいくつかのテストケースで欠陥を見つけることができました。

2. 入力を配列に格納し、すでに追加されている番号に隣接していないことを条件に、残りの最大数を追加しようとするたびに、このアルゴリズムも間違っていることが判明しました。

今、私が考えることができる唯一の解決策は、すべての可能な組み合わせを試すことによって指数関数的です:(

この問題を解決するための正しいアルゴリズムを提案してください。

Answer 1

これは、追加の制約（2つの隣接するブッシュを選択できない）を伴うKNAPSACK問題であり、追加の制約によって簡単にも困難にもなりません。KNAPSACK、つまりNP完全と同じくらい難しいので、ブルートフォース検索（最適化することはできますが、とにかく指数関数的/超多項式のままです）を除いて、本質的に他に行うことはほとんどありません。

Answer 2

これはよく知られた NP 困難な問題なので、解が指数関数的であっても心配する必要はありません。