next_permutation c++ 中 multimap 的使用

Question

我只是想以一种朴素的方式实现背包问题，以对我的原始解决方案进行压力测试。

我的代码

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;

我的观察

next_permutation() 正在创建错误，但我不明白为什么。
next_permutation()需要双向迭代器，multimap迭代器是双向迭代器。
我怀疑 multimap 总是排序的，这就是显示错误的原因??

请帮忙。感谢您。

Answer 1

您不能使用 std::map 或 std::multimap（或无序版本），因为 std::next_permutation 要求：

-BidirIt must meet the requirements of ValueSwappable and LegacyBidirectionalIterator.

但 std::multimap 值不可交换，因为映射中的键不可变：

value_type std::pair<const Key, T>

（重点是我的）

地图中元素的非正式顺序已确定，我无法更改。您必须使用 std::vector 等不同的容器来执行此操作。

next_permutation c++ 中 multimap 的使用

Usage of multimap with next_permutation c++

c++

stl

multimap