候補リストがあれば、線形時間で目標値に達することができますか？

Question

最近私はこの質問をしました。私はそれを爆破し、私はそれにいくつかの助けが好きです。質問は次のようになりました。

数字のリストが表示されます。数字はすべて正の整数です。だから我々はn番号を持っている

[x_0, x_1, ..., x_{n-2}, x_{n-1}] 

：だから彼らにこのようなものを想像してみてください。数字が異なるという保証はありません。目標値もあります。これをXとしましょう。 Xも正の整数です。私たちは、次の形式で候補者の観点から目標数、Xを、表現することができるかどう

目標は、出力にブールだけTrue/Falseです：

a * x_0 + b * x_1 + ... 

係数のための唯一の制約は、これらのこともあります

候補の数値で数学を少し行うだけで、線形時間で答えを得ることができます。しかし、アルゴリズムが少し複雑になっているのが分かりました。それはコード化する必要はありません - 私はそれを行うことができます - しかし、私はまだ正確にアルゴリズムを持っていません。私は多分Sieve of Eratosthenesへのアプローチで、あるいは多分Diophantine Equationに似た何かを考えていました。それにもかかわらず、私はどこでもオンラインで解決策のクリーンアップを見つけることができず、この問題がもっと探求されたのか不思議でした。

誰もが考えていますか？再度、感謝します！本当に助けていただきありがとうございます！ふるいを使用して

Answer 1

ソリューションは、このようなものになります：

はゼロtrueに設定され、falseに設定されたすべての他の値で、サイズのX + 1とブールの配列を作成します。 X _Iが既に（前回の数字の組み合わせは_{にx iは}とそのすべての倍数を形成するために使用することができる）がtrueに設定されている場合、X _I

• すべての値に対して次の値にスキップ。他
• 、（0〜X-X _I）アレイを反復X _K + X _I trueに設定し、真であるすべての値X _Kために、。
• 値Xがtrueに設定されるとtrueを返します。

小さな値から大きな値に最初に値をソートすると、値をスキップできる可能性が高くなります。

例：

X = 21, x = {4, 6, 8, 10, 11, 13, 15} 

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 
{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0} 

x = 4: 
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 
{1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0} 

x = 6: 
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 
{1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0} 

x = 8: skip 

x = 10: skip 

x = 11: 
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 
{1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1} 
10 + 11 = 21 -> return true 

最悪の場合（値は、結果が偽で、スキップしない）最良の場合に（xの最初の値は、Xが分割）しながら、この複雑さは、N × Xである溶液でありますほぼ即座に発見された。平均的なケースの複雑さを計算することは簡単ではありません。