Temukan kemungkinan angka dalam array yang dapat dijumlahkan ke nilai target

Mengingat saya memiliki serangkaian angka misalnya [14,6,10] - Bagaimana saya bisa menemukan kemungkinan kombinasi/pasangan yang dapat menambahkan hingga nilai target yang diberikan.

misalnya saya punya [14,6,10], saya mencari nilai target 40 output yang saya harapkan adalah

 10 + 10 + 6 + 14
 14 + 14 + 6 + 6
 10 + 10 + 10 + 10

* Urutan tidak penting

Karena itu, inilah yang saya coba sejauh ini:

function Sum(numbers, target, partial) {
  var s, n, remaining;

  partial = partial || [];

  s = partial.reduce(function (a, b) {
    return a + b;
  }, 0);

  if (s === target) {
     console.log("%s", partial.join("+"))
  }


  for (var i = 0; i < numbers.length; i++) {
    n = numbers[i];
    remaining = numbers.slice(i + 1);
    Sum(remaining, target, partial.concat([n]));
  }
}

>>> Sum([14,6,10],40);
// returns nothing

>>> Sum([14,6,10],24);
// return 14+10

Sebenarnya tidak ada gunanya karena hanya akan kembali jika angka tersebut hanya dapat digunakan sekali untuk menjumlahkan.

Jadi bagaimana cara melakukannya?


javascript sum algorithm
person user7716943    schedule 09.02.2019    source sumber
comment
apakah kamu juga mempunyai angka negatif?   -  person Nina Scholz    schedule 09.02.2019
comment
@Nina hanya angka positif tidak ada negatif   -  person user7716943    schedule 09.02.2019
comment
[14,6,10], jadi apakah panjang+1 yaitu kombinasi 4 angka? Juga, bagaimana jika Anda memiliki duplikat di array Anda   -  person Monica Acha    schedule 09.02.2019

Jawaban (2)


arrow_upward
5
arrow_downward

Anda dapat menambahkan nilai indeks sebenarnya selama jumlahnya lebih kecil dari jumlah yang diinginkan atau melanjutkan ke indeks berikutnya.

function getSum(array, sum) {
    function iter(index, temp) {
        var s = temp.reduce((a, b) => a + b, 0);
        if (s === sum) result.push(temp);
        if (s >= sum || index >= array.length) return;
        iter(index, temp.concat(array[index]));
        iter(index + 1, temp);
    }

    var result = [];
    iter(0, []);
    return result;
}

console.log(getSum([14, 6, 10], 40));
.as-console-wrapper { max-height: 100% !important; top: 0; }

Untuk mendapatkan kumpulan hasil terbatas, Anda dapat menentukan panjangnya dan memeriksanya di kondisi keluar.

function getSum(array, sum, limit) {
    function iter(index, temp) {
        var s = temp.reduce((a, b) => a + b, 0);
        if (s === sum) result.push(temp);
        if (s >= sum || index >= array.length || temp.length >= limit) return;
        iter(index, temp.concat(array[index]));
        iter(index + 1, temp);
    }

    var result = [];
    iter(0, []);
    return result;
}

console.log(getSum([14, 6, 10], 40, 5));
.as-console-wrapper { max-height: 100% !important; top: 0; }

person Nina Scholz    schedule 09.02.2019
comment
persis apa yang saya butuhkan! - person user7716943; 09.02.2019
comment
satu hal, jika saya suka getSum([1, 2, 3], 20) bagaimana cara saya secara eksplisit hanya menampilkan hasil jika panjang array sama/lebih rendah dari x? - person user7716943; 09.02.2019
comment
tambahkan kondisi di sini: if (s >= sum || index >= array.length || temp.length >= x) return; ini adalah kondisi keluar untuk resursion. - person Nina Scholz; 09.02.2019

arrow_upward
5
arrow_downward

TL&DR : Lewati ke Bagian II untuk mengetahui hal sebenarnya

Bagian I

Jawaban @Nina Scholz untuk masalah mendasar ini hanya menunjukkan kepada kita manifestasi indah dari suatu algoritma. Sejujurnya itu sangat membingungkan saya karena dua alasan

  1. Saat saya mencoba [14,6,10,7,3] dengan target 500, ia membuat 36.783.575 panggilan ke fungsi iter tanpa merusak tumpukan panggilan. Namun memori tidak menunjukkan penggunaan yang signifikan sama sekali.
  2. Solusi pemrograman dinamis saya berjalan sedikit lebih cepat (atau mungkin tidak) tetapi tidak ada cara yang dapat dilakukan di atas tanpa menghabiskan memori 16GB.

Jadi saya mengesampingkan solusi saya dan mulai menyelidiki kodenya sedikit lebih jauh pada alat pengembang dan menemukan keindahannya dan juga sedikit kekurangannya.

Pertama, saya percaya pendekatan algoritmik ini, yang mencakup penggunaan rekursi yang sangat cerdas, mungkin pantas mendapatkan namanya sendiri. Ini sangat hemat memori dan hanya menggunakan memori untuk kumpulan hasil yang dibuat. Tumpukan secara dinamis tumbuh dan menyusut terus menerus hingga mendekati batasnya.

Masalahnya adalah, meskipun sangat efisien, ia masih melakukan panggilan redundan dalam jumlah besar. Jadi jika dilihat lebih dalam, dengan sedikit modifikasi, 36.783.575 panggilan ke iter dapat dikurangi menjadi 20.254.744... seperti 45% yang menghasilkan kode yang jauh lebih cepat. Soalnya array masukan harus diurutkan menaik.

Jadi inilah versi modifikasi dari algoritma Nina. (Bersabarlah.. perlu waktu sekitar 25 detik untuk menyelesaikannya)

function getSum(array, sum) {
    function iter(index, temp) {cnt++ // counting iter calls -- remove in production code
        var s = temp.reduce((a, b) => a + b, 0);
        sum - s >= array[index]   && iter(index, temp.concat(array[index]));
        sum - s >= array[index+1] && iter(index + 1, temp);
        s === sum                 && result.push(temp);
        return;
    }

    var result = [];
    array.sort((x,y) => x-y); // this is a very cheap operation considering the size of the inpout array should be small for reasonable output.
    iter(0, []);
    return result;
}
var cnt = 0,
    arr = [14,6,10,7,3],
    tgt = 500,
    res;
console.time("combos");
res = getSum(arr,tgt);
console.timeEnd("combos");
console.log(`source numbers are ${arr}
found ${res.length} unique ways to sum up to ${tgt}
iter function has been called ${cnt} times`);

Bagian II

Meskipun saya terkesan dengan kinerjanya, saya merasa tidak nyaman dengan solusi di atas tanpa alasan kuat yang dapat saya sebutkan. Cara kerjanya pada efek samping dan rekursi ganda yang sangat sulit dipahami dan itu mengganggu saya.

Jadi inilah pendekatan saya terhadap pertanyaan ini. Ini berkali-kali lebih efisien dibandingkan dengan solusi yang diterima meskipun saya akan berfungsi di JS. Kami masih memiliki ruang untuk membuatnya sedikit lebih cepat dengan cara-cara yang sangat mendesak.

Perbedaannya adalah;

Angka yang diberikan: [14,6,10,7,3] Jumlah Target: 500

Jawaban yang Diterima:

  • Jumlah kemungkinan jawaban: 172686
  • Diselesaikan dalam: 26357ms
  • Jumlah panggilan rekursif: 36783575

Jawaban Di Bawah

  • Jumlah kemungkinan jawaban: 172686
  • Diselesaikan dalam: 1000ms
  • Jumlah panggilan rekursif: 542657

function items2T([n,...ns],t){cnt++ //remove cnt in production code
    var c = ~~(t/n);
    return ns.length ? Array(c+1).fill()
                                 .reduce((r,_,i) => r.concat(items2T(ns, t-n*i).map(s => Array(i).fill(n).concat(s))),[])
                     : t % n ? []
                             : [Array(c).fill(n)];
};

var cnt = 0, result;
console.time("combos");
result = items2T([14, 6, 10, 7, 3], 500)
console.timeEnd("combos");
console.log(`${result.length} many unique ways to sum up to 500
and ${cnt} recursive calls are performed`);

Hal penting lainnya adalah, jika array tertentu diurutkan secara menurun maka jumlah iterasi rekursif akan berkurang (terkadang sangat banyak), memungkinkan kita untuk memeras lebih banyak jus dari lemon ini. Bandingkan di atas dengan di bawah ketika array input diurutkan menurun.

function items2T([n,...ns],t){cnt++ //remove cnt in production code
    var c = ~~(t/n);
    return ns.length ? Array(c+1).fill()
                                 .reduce((r,_,i) => r.concat(items2T(ns, t-n*i).map(s => Array(i).fill(n).concat(s))),[])
                     : t % n ? []
                             : [Array(c).fill(n)];
};

var cnt = 0, result;
console.time("combos");
result = items2T([14, 10, 7, 6, 3], 500)
console.timeEnd("combos");
console.log(`${result.length} many unique ways to sum up to 500
and ${cnt} recursive calls are performed`);

person Redu    schedule 27.03.2019