における配列値の組み合わせの合計を取得します。..私はこれにいくつかの同様の質問があったことを知っているが、それでも私はそれを聞いてきます、これに決定的な答えがあるようには思えない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の関数型プログラミング機能を利用したりすることで、どのようにこれを行うでしょうか?
これは知られているソリューションで、ナップザック問題のバリエーションのように思える:https://en.wikipedia.org/wiki/Knapsack_problem – pedrorijo91
それはになりそうだが、それはどのようにの質問に答えていません多くの配列値を使用し、**メモリヒープエラーを引き起こさない効率的なソリューションをコード化してください** –