Задача на выборку - C++ - Ответ 16925386

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
 
using namespace std;
 
//https://www.cyberforum.ru/cpp-beginners/thread3109171.html
//Задача на выборку
//в С++ std практически нет алгоритмов для комбинаторики
//полистав интернет и приложив руки я наваял вот такую кучку)
 
size_t fact(size_t n)
{
    size_t res=1;
    for(size_t i=1; i<=n;++i)
    {
        res*=i;
    }
    return res;
}
 
size_t C_N_K(size_t n, size_t k)
{
    return fact(n)/(fact(n-k)*fact(k));
}
 
 
 vector <vector<int>> comb(int N, int K)
 {
     string bitmask(K, 1);
     bitmask.resize(N, 0);
     vector <int> v;
 
     vector <vector<int>> res;
     do {
          v.reserve(N);
          for (int i = 0; i < N; i++)
            {
               if (bitmask[i]) v.push_back(i+1);
            }
            v.shrink_to_fit();
 
             res.emplace_back(move(v));
             v.clear();
 
        } while (prev_permutation(bitmask.begin(), bitmask.end()));
 
        return res;
}
 
vector<int> comb(int N, int K, int n)
{
 string bitmask(K, 1);
 bitmask.resize(N, 0);
 
 vector <int> v;
 
 do {
        v.reserve(N);
 
            for (int i = 0; i < N; i++)
            {
 
                if (bitmask[i])
                 if(0==n) v.push_back(i+1);
            }
             v.shrink_to_fit();
              if(0==n) return v;
            --n;
            v.clear();
 
 
    } while (prev_permutation(bitmask.begin(), bitmask.end()));
 
    return v;
}
 
 
struct helper_comb_ordered
{
    //в контексте задачи для идентификации С_N_K нужен лишь K
    //поскольку N всегда постоянен (для множества из 5-ти книг это 5)
    size_t K;//размер выборки в сочетании С из N по K
    //для идентификации подмножества нужен ещё порядковый номер выборки в серии C_N_K:
    size_t n;//порядковый номер в серии сочетаний C_N_K
    size_t summa;
 
    helper_comb_ordered(size_t K_, size_t n_, size_t summa_)
    :K(K_)
    ,n(n_)
    ,summa(summa_)
    {
 
    }
 
    bool operator<(helper_comb_ordered const &other)
    {
        return summa<other.summa;
    }
    //для отладки пригодился - можно удалить
    friend
    ostream& operator<<(ostream &os, helper_comb_ordered const &other);
};
 
    //для отладки пригодился - можно удалить
    ostream& operator<<(ostream &os, helper_comb_ordered const &other)
    {
        return os<<other.K<<' '<<other.n<<' '<<other.summa<<'\n';
    }
 
int main()
{
    //тест перестановочных алгоритмов - можно удалить
    cout<<"combinatorics test\n\n";
      auto vres_all = comb( 10,  4);
      for(const auto& v:vres_all )
      {
          for(auto a:v)
          {
              cout<<a<<' ';
          }
          cout<<'\n';
      }
      cout<<'\n'<<'\n';
 
      auto v=comb(10, 4, 5);//5 вариант сочетаний из 10 по 4
          for(auto a:v)
          {
              cout<<a<<' ';
          }
          cout<<"\n\nthe end of combinatorics test\n\n";
            //алгоритм не хранит индексы всех перестановок, чтобы потом считать суммы на лету
            //а сохраняет лишь
            //реквизиты серии перестановки, номер в серии и сумму по ней - для ускорения
            //поиска lower_bound
 
                 cout<<"task of 5 books ";
                 const int set_size_ = 5;
                 using book_name_t=string;
                 using cost=size_t;
                 vector<pair<book_name_t, cost> > prise_list
                 {
                     {"Grimm Brothers", 323},
                     {"Astrid Lindgren", 246},
                     {"Andersen", 218},
                     {"Giani Rodari", 456},
                     {"Charles Pierrot", 300}
                 } ;
 
                 vector<helper_comb_ordered>seria;
 
                 for(size_t i=0; i<set_size_; ++i)
                 {
                    //C of N=set_size_ per K = 1
                    auto subsets_number= C_N_K(set_size_, i);
 
                    cout<<"subsets_number="<<subsets_number<<'\n';
 
                    for(size_t j=0; j<subsets_number; ++j )
                    {
                        auto next_comb_vec= comb(set_size_, i, j);
                        auto summa=0;
                        for(auto a:next_comb_vec)
                        {
                            summa+=prise_list[a-1].second;
                        }
                        seria.emplace_back(i,j,summa);
                        cout<<i<<' '<<j<<' '<<summa<<'\n';
                    }
                 }
 
                sort(seria.begin(), seria.end());
 
                //test value
                size_t test_sum = 856 ;
                 //size_t test_sum = 764 ;
 
                helper_comb_ordered test_hc{0,0,test_sum} ;
                auto it=lower_bound(seria.begin(), seria.end(), test_hc);
                if(it->summa>test_sum)--it;//summa не больше верхней планки
 
                 //искомая перестановка
                auto vec= comb(set_size_, it->K, it->n);
                cout<<'\n'<<'\n';
 
                cout<<"The whole amount of money (limited by: "<<test_sum<<") to buy those books is "<<(it->summa)<<"\n\n";
 
                for(auto a:vec)
                cout<<prise_list[a].first<<'\t'<< prise_list[a].second<<'\n';
 
                return 0;
}