具有next_permutation c ++的多图的使用

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;

我的观察

1. next_permutation（）正在创建错误，但是为什么我不明白为什么。

2. next_permutation（）需要双向迭代器，而多图迭代器是双向迭代器。

3. 我怀疑多图总是被排序，这就是为什么显示错误的原因？

请帮助。感谢您。

Answer 1

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

std::next_permutation
但是-BidirIt must meet the requirements of ValueSwappable and LegacyBidirectionalIterator.
值不可交换，因为映射中的键是不可变的：