Различные способы суммирования конкретных чисел для получения 100

Question

Я хочу написать код, показывающий, как можно суммировать 5 различных чисел, чтобы получить 100. Например, числа равны 2,5,10,20,50, и их можно повторять любое количество раз.Здесь 50+50 является односторонним и 20+20+20+20+20.Я понятия не имею, как это запрограммировать.

Я думаю, что это должно быть сделано с помощью рекурсивной функции, и я попытался написать ее, не зная, как это сделать, так что это лучшее, что я придумал:

#include<iostream>
#include<vector>

using namespace std;


int i,sum,n=5,counter=0;


int add(vector<int> &m){

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

    for(i=0 ; i<m.size() ; i++ ){

          sum=m[i]+add(m);
          cout<< sum<<endl;
        if(n>0) n--;
        m.resize(n);
    }


}


int _tmain(int argc, _TCHAR* argv[])
{
    int i,sum,n=5;

vector<int> m;

m.resize(5);

m[0]=2;
m[1]=5;
m[2]=10;
m[3]=20;
m[4]=50;

add(m);


    return 0;
}

Answer 1

Эта проблема может быть решена теоретически с помощью производящих функций .Генерирующая функция не является функцией и ничего не генерирует (доброе имя, а?), Но она очень хорошо отслеживает информацию.В результате ответ на вашу проблему состоит в том, что число путей равно коэффициенту x^100 при расширении

1/(1-x^2) * 1/(1-x^5) * 1/(1-x^10) * 1/(1-x^20) * 1/(1-x^50) 

Вот объяснение, почему.Напомним, что 1/(1-x) = 1 + x + x^2 + x^3 + ....Это основная генерирующая функция, которую мы собираемся использовать для решения проблемы.

Учтите, что у вас есть числа A, B, ..., N (в вашем примере они равны 2,5,10, 20,50), что вы можете повторить любое количество раз.Затем рассмотрим (производящую) функцию

f(x) = 1/(1-x^A) * 1/(1-x^B) * ... * 1/(1-x^N)

Коэффициент x^M в f(x) представляет собой количество способов записать M как сумму вида

M = a*A + b*B + ... + n*N

, где a,b,...,n - неотрицательные целые числа.

Почему это работает? Поскольку любой мономиальный термин в расширении f(x) происходит от взятия одного термина из 1/(1-x^A), который будет выглядеть как x^(a*A) для некоторого неотрицательного a,и аналогично для других терминов.Поскольку показатели добавляются, коэффициент x^M - это все способы составления такой суммы, чтобы получить M.

Я знаю, что это не программный ответ, но, надеюсь, вы сможете использовать эту идею длянаписать программу.

Answer 2

просто для удовольствия

#include <iostream>
#include <vector>
#include <iterator>
#include <numeric>
#include <algorithm>

static const int terms[] = { 2,5,10,20,50,   /*end marker*/0 };

using namespace std;
typedef vector  <int> Solution;
typedef vector  <Solution> Solutions;

inline int Sum(const Solution& s)
{
    return accumulate(s.begin(), s.end(), 0);
}

template <typename OutIt>
    OutIt generate(const int target, const int* term, Solution partial, OutIt out)
{
    const int cumulative = Sum(partial); // TODO optimize

    if (cumulative>target)
        return out;         // bail out, target exceeded

    if (cumulative == target)
    {
        (*out++) = partial; // report found solution
        return out;
    } else
    {
        // target not reached yet, try all terms in succession
        for (; *term && cumulative+*term<=target; term++)
        {
            partial.push_back(*term);
            out = generate(target, term, partial, out); // recursively generate till target reached
            partial.pop_back();
        }
        return out;
    }
}

Solutions generate(const int target)
{
    Solutions s;

    generate(target, terms, Solution(), back_inserter(s));

    return s;
}

void Dump(const Solution& solution)
{
    std::copy(solution.begin(), solution.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
}

#ifdef _TCHAR
int _tmain(int argc, _TCHAR* argv[])
#else
int main(int argc, char* argv[])
#endif
{
    Solutions all = generate(100);
    for_each(all.rbegin(), all.rend(), &Dump);
    return 0;
}

$ 0,02

---

Чтобы действительно ответить на вопрос, я удалил все ненужные выходные данные решений, значительно оптимизировав код. Теперь он намного эффективнее (я тестировал его в 25 раз быстрее с target=2000) , но он все еще не масштабируется до больших target s ...

#include <iostream>
#include <vector>

using namespace std;

size_t generate(const int target, vector<int> terms)
{
    size_t count = 0;

    if (terms.back()<=target)
    {
        int largest = terms.back();
        terms.pop_back();
        int remain = target % largest;

        if (!remain)
            count += 1;

        if (!terms.empty())
            for (; remain<=target; remain+=largest)
                count += generate(remain, terms);
    }

    return count;
}

int main(int argc, char* argv[])
{
    static const int terms[] = {2,5,10,20,50};
    std::cout << "Found: " << generate(1000, vector<int>(terms, terms+5)) << std::endl;
    return 0;
}

Надеемся, что более умная арифметика по модулю начинает отражать то, что PengOne предложил по поводу решения этой проблемы.

Answer 3

Вот рекурсивное решение: http://ideone.com/ip98M

#include <iostream>

template<size_t N>
void find_combinations_helper(int total, const int (&denoms)[N], int denoms_used, int remaining, int (&counts)[N])
{
    if (remaining == 0) {
        int partial_sum = 0;
        for( int i = 0; i < denoms_used; ++i ) {
           if (counts[i]) {
               std::cout << counts[i] << "*" << denoms[i];
               partial_sum += counts[i] * denoms[i];
               if (partial_sum < total) std::cout << " + ";
           }
        }
        std::cout << "\n";
        return;
    }

    if (denoms_used == N) return;

    for( counts[denoms_used] = 0; remaining >= 0; (remaining -= denoms[denoms_used]), ++counts[denoms_used] )
        find_combinations_helper(total, denoms, denoms_used + 1, remaining, counts);
}

template<size_t N>
void find_combinations( int total, const int (&denoms)[N] )
{
    int solutions[N];
    find_combinations_helper(total, denoms, 0, total, solutions);
}

int main(void) {
    const int bill_denoms[] = { 50, 20, 10, 5, 2 };
    find_combinations(100, bill_denoms);
}

Answer 4

Код, который у вас есть на данный момент для функции add, приведет к переполнению стека :) Потому что вы делаете рекурсивный вызов add(m) перед изменением вектора m. Таким образом, add вызывается всегда с неизмененным вектором, а базовый случай никогда не ударит.

Я не знаю, поймал ли я, что вы хотите сделать, но как насчет:

#include <iostream>
#include <sstream>
#include <vector>

void add(int i, std::string s, int sum)
{
    if (sum == 100)
    {
      std::cout << s << "=100" << std::endl;
      return;
    }
    if (sum > 100)
    {
       return;
    }
    if (sum < 100)
    {
      std::ostringstream oss;
      oss << s << "+" << i;
      add(i, oss.str(), sum+i);
    }
}

int main()
{
  std::vector<int> m;

  m.resize(5);

  m[0]=2;
  m[1]=5;
  m[2]=10;
  m[3]=20;
  m[4]=50;

  // This loop will initiate m.size lines of recursive calls
  // one for each element of the array
  for (size_t i = 0; i < m.size(); i++)
  {
    add(m[i], "", 0);
  }

  return 0;
}

Answer 5

Это выглядит не так:

m[0]=2;
...
m[0]=50;

Не должно ли быть м [4] = 50;?

Редактировать Вы никогда не объявляете значение 100, откуда вы знаете, когда вы достигли 100?