平衡パーティションの欲張りのアプローチ

Question

私は平衡パーティショニングの問題hereとhere (problem 7)を見ていました。

問題は基本的に、数値の合計の絶対差がS1であるように2つのサブセット（S1とS2）に分割することを求めています。ans S2 |sum(S1) - sum(S2)|は最小である必要があります。私が理解できなかったことは、誰も欲張りなアプローチを提案しない理由は何ですか：

def balanced_partition(lst): 
    idx = 0 
    S1 = 0 
    S2 = 0 
    result_partition=[None]*len(lst) 
    while idx < len(lst): 
     new_S1 = S1 + lst[idx] 
     new_S2 = S2 + lst[idx] 
     if abs(new_S1 - S2) < abs(new_S2 - S1): 
      result_partition[idx] = 1 
      S1 = new_S1 
     else: 
      result_partition[idx] = 2 
      S2 = new_S2 
     idx += 1 
    print("final sums s1 = {S1} and s2 = {S2} ".format(S1=S1, S2=S2)) 
    return result_partition 

私のアプローチには何が間違っていますか？私が思いつくことができるすべてのテストケースに合格したようです。

Answer 1

単純な反例は[1,1,1,1,1,1,6]です。欲張りのアプローチは、2つのセットの間にそれらを広げ、最適解は[1,1,1,1,1,1],[6]です。

Answer 2

実装とアプローチに問題はありません。しかし、この特定の問題ですべてのサブセットを考慮すると、貪欲な出力よりも良い答えが見つかるかもしれません。あなたが共有しているwikiページでさえ、いくつかの例があります。

おそらく、あなたはすでにこれら2つのアプローチの違いを知っています。貪欲なアルゴリズムは、あなたには常に良い結果を与えるでしょうが、それに近いか、あるいは最良のものと同じであれば、すべてのオプションを確実に考慮する必要があります。動的プログラミングアプローチは、可能なすべてのサブセットをある方法でチェックします。以前に計算されたサブ問題の結果を保存するので、基本的にブルートフォースよりも高速です。

質問は、欲張りや動的プログラミングのアプローチを使用する場合です。私はいくつかの競争の激しいプログラミングを行っています。私はDP問題（パーティション化、サブセット合計、ナップザックなどの問題）を見たときに、時にはほとんどの場合、より鮮明な解決策を思いつきます。人々は日常生活の中で常に貪欲なアプローチを使用しています。実装する前に、アルゴリズムを例題でテストし、正しいアプローチであることを自分自身で確信したら実装します。これは、なんらかの意味で直感的です。

もっと良い答えが必要なテストケースが見つかった場合は、おそらくDPソリューションを見つけなければならない可能性があります。裁判官システムからWAを取得した場合は、良いテストケースが見つからないことを意味しますが、それは正しいテストケースを見つける必要はありません。これは、より良い解決策を見つけるのに役立たないためです。