2017-04-15 11 views
0

における配列値の組み合わせの合計を取得します。..私はこれにいくつかの同様の質問があったことを知っているが、それでも私はそれを聞いてきます、これに決定的な答えがあるようには思えないScalaの

I arrayの値を持ち、合計値がlimitである正しい値を見つけようとしているか、または与えられた組み合わせから(それを超えずに)得ることができる最も近い値を見つけようとしています。

この回答https://stackoverflow.com/questions/23168934/calculating-minimal-subset-with-given-sumを使用して、私はこれがあります。

def getLimitArr(arr: Array[Int], limit: Int): Unit = { 

     scala.util.Sorting.quickSort(arr) // Array(2, 3, 4, 5, 11, 34) 
     var sum = 0L 
     var i = arr.length-1 

     val arr2 = ArrayBuffer[Integer]() 
     while (i >= 0 && sum < limit) { 
     if(sum + arr(i)<=limit) { 
      sum += arr(i) 
      arr2 += arr(i) 
     } 
     i -= 1 // 6, 5, 4, 3, 2, 1 
     } 

    println(arr2.mkString(", ") + " = " + sum) 

    } 

をメインの方法でこれを使用して、それを呼び出す:

val arr = Array(3, 34, 4, 11, 5, 2) 
    getLimitArr(arr, 9) 

返します

println(arr2.mkString(", ") + " = " + sum) // 5, 4 = 9 

これは良いのですが、 (合計を構成する)値が、それよりも低い最高値から作成される場合にのみn限度。この例では5 - この配列で動作します。しかし、この配列の制限値が12(getLimitArr(arr, 12))の場合、5 + 4 + 3ではなく11 = 11を返します。

私はサブセットを使用して、これを行っているが、配列は、それが答えを得ることができるようになる前に、全ての組み合わせを策定されたとして、私はメモリヒープエラーを取得する10以上であるとき。

私たちはメモリを効率的に使用し、現在のフォーマットを使用したり、Scalaの関数型プログラミング機能を利用したりすることで、どのようにこれを行うでしょうか?

+0

これは知られているソリューションで、ナップザック問題のバリエーションのように思える:https://en.wikipedia.org/wiki/Knapsack_problem – pedrorijo91

+0

それはになりそうだが、それはどのようにの質問に答えていません多くの配列値を使用し、**メモリヒープエラーを引き起こさない効率的なソリューションをコード化してください** –

答えて

0

再帰は、最初の正解が見つかると直ちに終了したいときに便利です。 23

def getLimit(nums: Array[Int], limit: Int): Array[Int] = { 
    val subset = nums.filter(limit.>=) 
    if (subset.isEmpty) Array() 
    else (1 to subset.length).flatMap(subset.combinations) 
          .find(_.sum == limit) 
          .fold(getLimit(subset, limit-1))(identity) 
} 

getLimit(Array(3, 34, 4, 11, 5, 2), 5) // res0: Array[Int] = Array(5) 
getLimit(Array(3, 34, 4, 11, 5, 2), 9) // res1: Array[Int] = Array(4, 5) 
getLimit(Array(3, 34, 4, 11, 5, 2), 12) // res2: Array[Int] = Array(3, 4, 5) 
getLimit(Array(3, 34, 4, 11, 5, 2), 24) // res3: Array[Int] = Array(3, 4, 11, 5) 

注最後の和その24

更新

に合計ない組み合わせがないため、より良いショートカットを添加し、この方法は、現在尾再帰的です。

def getLimit(nums: Array[Int], limit: Int): Array[Int] = { 
    val subset = nums.filter(limit.>=) 
    if (subset.sum <= limit) subset 
    else { 
    val res = (1 to subset.length).view 
            .flatMap(subset.combinations) 
            .find(_.sum == limit) 
    if (res.isEmpty) getLimit(subset, limit-1) 
    else res.get 
    } 
} 
+0

ありがとうございますが、ソリューションが1つまたは2つだけを使用して見つからない場合は、java.lang.OutOfMemoryError:GCオーバーヘッドの上限を超えました**エラーが発生します。私は最大30個の配列値を扱うことができるものを探しています_ –

+0

@ jesusg_forceHarris、更新を参照してください。 – jwvh

+0

それは間違いなく良いことですが、それは価値ある答えですが、30の配列値を扱うことはできません。助けることはできませんが、よりリーンなソリューションがあると感じることができます –

関連する問題

 関連する問題