Помогите пожалуйста с задачей о рюкзаке на с++

Прекрасный пример задачи, на которой можно продемонстрировать разные способы решения.

Начнём с решения в лоб. Берём всевозможные подмножества элементов, складываем, проверяем сумму.

 unsigned f1(const vector& m, unsigned M) 

{ 

  unsigned r = 0; 

  for(unsigned i = 1; i < (1  M) { c = 0; break; } 

    } 

    if(s == M) 

      if(c > 0 && (r == 0 || r > c))  r = c; 

  } 

  return r; 

}  

Работает, однако легко видеть, что количество операций будет O(2^N), явно не годится по времени.

Попробуем другой подход. Введём функцию r(M, k), значениями которой будет наименьшее количество предметов, набирающих вес M, без учёта первых k предметов. Очевидно, что ответом на задачу будет r(M, 0). Функция удовлетворяет рекуррентным соотношениям

 r(M, k) = min( r(M, k+1), r(M-m[k], k+1) + 1 )

r(M, N) = 0

r(m[k], k) = 1 

(необходимая сумма набирается либо с применением m[k] и уменьшением требуемой суммы, либо без применения). Формулы немного усложняются для учёта нулевых значений, но это будет в любом решении.

 unsigned f2(const vector& m, unsigned M, unsigned k = 0) 

{ 

  if(k == m.size()) return 0; 

  if(M == m[k]) return 1; 

  unsigned r1 = f2(m, M, k+1); 

  unsigned r2 = M > m[k] ? f2(m, M - m[k], k+1) : 0; 

  return r2 > 0 && (r1 == 0 || r1 > r2) ? r2 + 1 : r1; 

} 

Стало покороче, но количество операций осталось таким же, O(2^N). Можно ли как-то его уменьшить?

Расширим немного задачу. Будем считать количество предметов, необходимых для набора не только M, но и всех чисел от 1 до M. Удивительно, но решение такой расширенной задачи оказывается проще и быстрее, хотя основная формула не изменяется.

 unsigned f3(const vector& m, unsigned M) 

{ 

  std::vector r(M+1); 

  for(unsigned x : m) 

  { 

    for(unsigned s = M; s > x; --s) 

      if(r[s-x] > 0 && (r[s] == 0 || r[s] > r[s-x])) 

        r[s] = r[s-x] + 1; 

    r[x] = 1; 

  } 

  return r[M]; 

} 

Теперь количество операций составляет O(NM), что должно удовлетворить любую тестирующую систему.