入力シーケンスで表現できない最小数を見つける方法

Question

ここにインタビューの質問があります： 入力： 整数N;異なる正の整数a1、a2 ... aN;

出力： 最小正の整数mは、m = x1 * a1 + x2 * a2 + ... xN * aNの形式では表現できません。ここでxi = {0,1}です。

Answer 1

ナイーブ溶液：

public static void calcAllSums(int[] arr, int sum, int curIndex, Hashtable<Integer,Boolean> sums){ 
    if (curIndex == arr.length) return; 
    int sum1 = sum+arr[curIndex]; 
    int sum2 = sum; 
    sums.put(sum1, true); 
    sums.put(sum2, true); 
    calcAllSums(arr, sum1, curIndex+1, sums); 
    calcAllSums(arr, sum2, curIndex+1, sums); 
} 
public static void main(String[] args){ 
    int[] arr = {1,3,5}; 
    Hashtable<Integer,Boolean> sums = new Hashtable<Integer,Boolean>(); 
    calcAllSums(arr, 0, 0, sums); 
    int i=0; 
    while (sums.containsKey(i)) i++; 
    System.out.println(i); 
} 

iが非常に高速全和-の-3-番号コードするリスト

Answer 2

でない整数を見つけるまで私はすべての可能な和を計算し、反復、 Aliaksei Safryhinのコードを参照してください。

*pTo++ += short(*pFrom++) << 8; *pTo++ += short(*pFrom++) << 8; 

よう 一連のステートメントは、不器用なと遅いように見えますが、私のテストにシフトビットマップ方式よりも高速に何度も走ったことがあります。 Al Zimmermann's Son of DartsとHow can I improve this algorithm for solving a modified Postage Stamp puzzle?も参照し、2010年7月7日のJohn Morrisのdarts.pdfが見つかる場合は、3〜20の数字の最初の不足サブセット合計のかなり高速な列挙子のコードが含まれています。

Answer 3

二つの連続番号の間の最小の差が _N要素の少なくともあるので

、及び0私は言うだろう、表現可能である

分 _N（ _N） - 1

もちろん、min _n（a _n）= 1の場合は、2番目から最小の同様の推論を行うことができます。