Использование multimap с next_permutation c ++ - PullRequest
Новая
       55

Использование multimap с next_permutation c ++

1 голос
/ 06 мая 2020

Я просто пытаюсь реализовать задачу о ранце наивным способом, чтобы проверить свое исходное решение.

МОЙ КОД 

double StressTest(multimap<int, int> ValWt, int KnapscakWeight)
{
    vector<double> TotalValue;
    double Temp_KnapsackWeight = 0.0;
    double Value = 0.0;
    multimap<int, int>::iterator itr1;// = ValWt.begin();

    do
    {
        itr1 = ValWt.begin();
        Temp_KnapsackWeight = KnapscakWeight;
        while( (Temp_KnapsackWeight > 0) && (itr1 != ValWt.end()) )
        {
            if(itr1->second > Temp_KnapsackWeight)
            {
                Value += ( (Temp_KnapsackWeight/itr1->second) * itr1->first );
                Temp_KnapsackWeight = 0;
            }

            else
            {
                Temp_KnapsackWeight -= itr1->second;
                Value += itr1->first;
            }
            itr1++;
        }

        TotalValue.push_back(Value);
        Value = 0.0;

    }while( next_permutation(ValWt.begin(), ValWt.end()) );

    return *max_element(TotalValue.begin(), TotalValue.end());
}

ОШИБКА 

In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from 2_max_val_of_loot.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h: In instantiation of ‘void std::iter_swap(_ForwardIterator1, _ForwardIterator2) [with _ForwardIterator1 = std::_Rb_tree_iterator<std::pair<const int, int> >; _ForwardIterator2 = std::_Rb_tree_iterator<std::pair<const int, int> >]’:
/usr/include/c++/7/bits/stl_algo.h:2926:22:   required from ‘bool std::__next_permutation(_BidirectionalIterator, _BidirectionalIterator, _Compare) [with _BidirectionalIterator = std::_Rb_tree_iterator<std::pair<const int, int> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]’
/usr/include/c++/7/bits/stl_algo.h:2966:2:   required from ‘bool std::next_permutation(_BIter, _BIter) [with _BIter = std::_Rb_tree_iterator<std::pair<const int, int> >]’
2_max_val_of_loot.cpp:39:53:   required from here
/usr/include/c++/7/bits/stl_algobase.h:148:11: error: use of deleted function ‘typename std::enable_if<(! std::__and_<std::__is_swappable<_T1>, std::__is_swappable<_T2> >::value)>::type std::swap(std::pair<_T1, _T2>&, std::pair<_T1, _T2>&) [with _T1 = const int; _T2 = int; typename std::enable_if<(! std::__and_<std::__is_swappable<_T1>, std::__is_swappable<_T2> >::value)>::type = void]’
       swap(*__a, *__b);
       ~~~~^~~~~~~~~~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:64:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from 2_max_val_of_loot.cpp:1:
/usr/include/c++/7/bits/stl_pair.h:503:5: note: declared here
     swap(pair<_T1, _T2>&, pair<_T1, _T2>&) = delete;

МОЕ НАБЛЮДЕНИЕ

  1. next_permutation () создает ошибку, но почему Я не понимаю, почему.

  2. next_permutation () требует двунаправленного итератора, а итератор с множеством карт является двунаправленным итератором.

  3. Я сомневаюсь, что мультикарта сортируется всегда, поэтому отображается ошибка ??

Пожалуйста, помогите. Спасибо.

1 Ответ

1 голос
/ 06 мая 2020

Вы не можете использовать std::map или std::multimap (или неупорядоченные версии), поскольку std::next_permutation требует: 

-BidirIt must meet the requirements of ValueSwappable and LegacyBidirectionalIterator.

, но значения std::multimap не могут быть заменены в качестве ключа в карта не изменяема:

value_type std :: pair <<strong> const Key, T>

(курсив мой)

Менее формально порядок элементов на карте определен и не может быть изменен. Для выполнения этой операции вы должны использовать другой контейнер, например std::vector.

...