Подсчитайте целые разделы с k частями, когда заданы элементы раздела

Я хочу подсчитать целые разделы n с k элементами раздела. Возможные элементы раздела определяются через данный вектор v с различными элементами. Элементы перегородки можно выбирать более одного раза. Как я могу это сделать? Оптимально без повторения всех целочисленных разделов n.

Пример:

n := 10

k := 3

v := 1,2,6,7,8

=> 3


algorithm math dynamic-programming subset-sum integer-partition
person TTho Einthausend    schedule 19.02.2020    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Один из способов - заставить повторение рассматривать каждый элемент по порядку.

Незапоминаемый JavaScript:

function f(n, k, v, i=0){
  if (k == 0)
    return n == 0;

  if (i == v.length)
    return false;
  
  let total = 0
  
  while (k >= 0 && n >= 0){
    total = total + f(n, k, v, i+1);
    k = k - 1;
    n = n - v[i];
  }
  
  return total;
}

console.log(f(10, 3, [1,2,6,7,8]));

person גלעד ברקן    schedule 20.02.2020