Как сделать алгоритм перебора всех вариантов перестановок и количества чисел, чтобы их сумма ровнялась определенному числу?

Question

[ruldo]

Пишу хитрый калькулятор на сайт и столкнулся с такой проблемой:
Есть некоторая высота, допустим 3000, нужно её составить из элементов 1000, 750 и 500 всеми возможными способами.

Перелопатил кучу алгоритмов, но везде только перебор известного количества элементов, в моём случае количество элементов будет разное (3 элемента: 1000 + 1000 + 1000; 4 элемента: 750 + 750 + 1000 + 500 и т.д)
Как реализовать такой алгоритм?

Comments

[Максим Федоров]

у вас точно не больше 6 элементов: 500x6

Answer 1

[Алексей Ярков]

https://jsfiddle.net/yarkov_aleksei/jwnrbyoc/

const sizes = [1000, 750, 500]
const sum = 3000

function permutation(len, acc = []){
  let res = []
  sizes.forEach(s => {
    let temp = null
    if (s === len) {
      res.push(acc.concat([s]))
    } else if (s < len) {
      temp = permutation(len-s, acc.concat([s]))
    }
    if (temp) {
      res = res.concat(temp)
    }
  })
  if (res.length) {
    return res
  }
 }

 const result = permutation(sum)
 console.log(result)

Answer 2

[#]

вашу задачу можно рассмотреть как аналог раскроя ленты материала (длиной 3000 единиц измерения) на отрезы заданной длины (1000, 750 и 500)

тогда уже понятно куда копать Задача раскроя

больше не подскажу, у к сожалению сам ни когда не сталкивался с реализациями