同じ長さの2行のC++アルゴリズム

Question

私はこのような問題を解決する良い方法を見つけることができません。 私たちは5 < = k < = 1〜1000単位の長さのセグメントを持っています。 プログラムは、これらのセグメントから同じ長さの2つのピラーを構築する必要があります。 プログラムは、可能な限りの長さのピラーを見つけなければなりません。

例： 5セグメントの長さ：1 5 2 3 4 正しい解決策は、第1ピラー2 + 5 = 7および第2ピラー3 + 4 = 7です。

どうすれば対処できますか？

Answer 1

ウィキペディアには、あなたのやりたいことのような鉛音が聞こえるthe Partition Problem in Computer Scienceに関する記事があります。コンピュータサイエンス、パーティションの問題（または番号のパーティション1） において

正 整数の所定の多重集合Sは2つの部分集合S1とS2に分割することができるかどうかを決定するタスクであるように 和S1の数字はS2の数字の合計と等しくなります。 パーティションの問題はNP完全ですが、擬似多項式 の時間動的プログラミングソリューションがあり、多くの場合、 という問題を最適または近似的に解決するヒューリスティックがあります。この理由のために のために、これは "最も簡単なNP困難な問題"と呼ばれています。

解決策を提供するいくつかの異なるアルゴリズムへの参照があります。

以下も参照してください。

Is partitioning an array into halves with equal sums P or NP?

3-PARTITION problem

custom partition problem

C++ Elegant solution to partition problem

Answer 2

これは、いくつかの奇妙なコードですが、それは仕事だん。 （小さなセットに最適です 、何の最適化は、このコードには適用されませんでした、遅い実行可能性、注意してください - x!複雑さ）

template<template<typename...> class Set = std::vector, 
     template<typename...> class Pair = std::pair, 
     template<typename...> class Cont, 
     typename... Ts> 
inline Set<Cont<Pair<typename Cont<Ts...>::value_type, size_t>>> all_subsets(const Cont<Ts...>& cont) 
{ 
    Set<Cont<Pair<typename Cont<Ts...>::value_type, size_t>>> all_subsets; 
    Cont<Pair<typename Cont<Ts...>::value_type, size_t>> empty; 
    all_subsets.push_back(empty); 

    for(auto it1 = cont.begin(); it1 != cont.end(); ++it1) 
    { 
     Set<Cont<Pair<typename Cont<Ts...>::value_type, size_t>>> temp_subset = all_subsets; 
     for(auto& it2 : temp_subset) 
      it2.push_back({*it1, std::distance(cont.begin(), it1)}); 
     for(const auto& it2 : temp_subset) 
      all_subsets.push_back(it2); 
    } 
    return all_subsets; 
} 

template<template<typename...> class Cont, 
     typename... Ts> 
inline bool intersects_by_second(const Cont<Ts...>& first, const Cont<Ts...>& second) 
{ 
    for(auto it1 : first) 
     for(auto it2 : second) 
      if(it1 == it2) 
       return true; 
    return false; 
} 

template<template<typename...> class Cont, 
     typename... Ts> 
inline Cont<typename Cont<Ts...>::value_type::first_type> make_vector_of_firsts(const Cont<Ts...> cont) 
{ 
    Cont<typename Cont<Ts...>::value_type::first_type> result; 
    for(const auto& it : cont) 
     result.push_back(it.first); 
    return result; 
} 

template<template<typename...> class Cont, 
     typename... Ts> 
inline Cont<typename Cont<Ts...>::value_type::second_type> make_vector_of_seconds(const Cont<Ts...> cont) 
{ 
    Cont<typename Cont<Ts...>::value_type::second_type> result; 
    for(const auto& it : cont) 
     result.push_back(it.second); 
    return result; 
} 

template<template<typename...> class Bag = std::vector, 
     template<typename...> class Pair = std::pair, 
     template<typename...> class Cont, 
     typename... Ts> 
inline Bag<Pair<Cont<Ts...>, Cont<Ts...>>> full_sum_partition(const Cont<Ts...>& cont) 
{ 
    auto subsets = all_subsets(cont); 

    Bag<Pair<Cont<Ts...>, Cont<Ts...>>> result; 

    for(auto it1 : subsets) 
     for(auto it2 : subsets) 
     { 
      auto it1_firsts = make_vector_of_firsts(it1); 
      auto it2_firsts = make_vector_of_firsts(it2); 
      if(std::accumulate(it1_firsts.begin(), it1_firsts.end(), 0) 
       == 
       std::accumulate(it2_firsts.begin(), it2_firsts.end(), 0)) 
      { 
       if(intersects_by_second(it1, it2) 
        || 
        it1.size() != it2.size()) 
        continue; 
       result.push_back(Pair<Cont<Ts...>, Cont<Ts...>> 
           (it1_firsts, 
            it2_firsts)); 
      } 
     } 
    return result; 
} 



int main() 
{ 
    std::vector<int> vec{1,4,9,16,25,36,49,64}; 
    auto result = full_sum_partition(vec); 

    for(const auto& x : result) 
     std::cout << x << " with sum " << std::accumulate(x.first.begin(), 
                  x.first.end(), 
                  0) << std::endl; 
} 

は出力：

([], []) with sum 0 
([1, 25, 36], [4, 9, 49]) with sum 62 
([16, 25, 36], [4, 9, 64]) with sum 77 
([4, 9, 49], [1, 25, 36]) with sum 62 
([16, 49], [1, 64]) with sum 65 
([4, 36, 49], [9, 16, 64]) with sum 89 
([1, 16, 36, 49], [4, 9, 25, 64]) with sum 102 
([1, 64], [16, 49]) with sum 65 
([4, 9, 64], [16, 25, 36]) with sum 77 
([9, 16, 64], [4, 36, 49]) with sum 89 
([4, 9, 25, 64], [1, 16, 36, 49]) with sum 102 
Press <RETURN> to close this window... 

はまた、私はオペレータ<をオーバーロードしていることに注意してくださいさまざまなコンテナの<、この出力は私の追加のファイルでのみ動作します。

for(const auto& x : result) 
{ 
    size_t i=0; 
    std::cout << "(["; 
    for(i=0; i< x.first.size(); ++i) 
     std::cout << x.first[i] << "],"[(i<x.first.size()-1)]; 
    if(i==0) 
     std::cout << ']'; 
    std::cout << ",["; 
    for(i=0; i< x.second.size(); ++i) 
     std::cout << x.second[i] << "],"[(i<x.first.size()-1)]; 
    if(i==0) 
     std::cout << ']'; 
    std::cout << ')' 
       << " with sum " << std::accumulate(x.first.begin(), 
               x.first.end(), 
               0) << std::endl; 
}