数字群を二つのグループに分けて、それぞれの合計値の差が最小になるアルゴリズムを知りたい。

Question

前にした質問と似ていますが、条件としては[2 2 2 3 3 4 5]のように数字群があり、それらの数字は重複しているものもあります。グループ１とグループ２に分けて、合計値の差が必ずしもゼロになるわけではないことが注意です。

まだ途中のコードで、前と同様にコンビネーション関数を使って解こうと考えたのですが、かなり非効率な方法だなとおもいましたが、一応書いてみたコードが下記のものにになります。

該当のソースコード

import itertools
min_diff = float('inf')
num = int(input())

lis =  [2 2 2 3 3 4 5]　   ##その他　数字群が様々あるが、、、
lis = [int(x) for x in lis ]
lis = sorted(lis)

group1=[]
group2=[]


for i in range(1,num):
    group1=[]   
    group2=[]
    lis2 = lis.copy()
    
    for c1 in itertools.combinations(lis2, i):
        c1 = list(c1)
        
        group1=[x for x in c1]
        print(sum(group1))
        for j in range(len(c1)):
          
            lis2.remove(c1[j])# ここでremoveの関数にはエラーが起こるが、、、
    
    group2=lis2
    diff =abs(sum(group1)-sum(group2))
    if diff ==0:
        break 
    
    elif  diff< min_diff:
        min_diff = diff
    else:
        continue
print(min_diff)

試したこと

他にも平均値を求めソートを使い、グループ１、グループ２に、小さい数字順に交互に入れていき、
平均値を超えた場合、余りをもう片方に入れて、合計値が大きいグループから小さいグループに、一番小さい数字を入れていくwhile文を作成したのですが、この最適化問題？では最小値が前回と同様になったらwhileを抜けると考えると、最小値が同じ数字（今回なら２）だと、ずっと交換し続けることになるので、うまく作成できませんでした。おそらくもっと効率のいい考え方があるのではと思うので、ご教授いただけたと思います。

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

Answer 1

グループ1とグループ2に分けたときに、合計値の差が最も小さくなる分け方を求めるという問題ですが、仮に合計の小さい方をグループ1とすることにすると、グループ1の合計は全体の合計の半分以下となります。
ここで、グループ1の選び方に注目すると、「全体の合計の半分以下の範囲で、グループ1の合計を最大いくつにすることができるか」という問題に帰着できます。

この問題は、「目標値が全体の合計の半分である部分和問題を動的計画法で解いて、解く際に使用したテーブルから、目標値以下で作成可能な最大の部分和を求める」という手順で解くことができます。

こちらの方針で解いたものが、以下のコードになります。

def min_diff(arr):
    s = sum(arr) // 2
    dp = [True] + [False] * s
    for i in range(len(arr)):
        for j in range(s, arr[i] - 1, -1):
            dp[j] = dp[j] or dp[j - arr[i]]
    for p in range(s, -1, -1):
        if dp[p]:
            return sum(arr) - 2 * p

実際の組み合わせを求めたい場合は、以下のようになります。

def min_diff(arr):
    s = sum(arr) // 2
    dp = [-1] + [None] * s
    for i in range(len(arr)):
        for j in range(s, arr[i] - 1, -1):
            if dp[j] is None and dp[j - arr[i]] is not None:
                dp[j] = i
    for p in range(s, -1, -1):
        if dp[p] is not None:
            break
    s1 = set()
    while p > 0:
        s1.add(dp[p])
        p -= arr[dp[p]]
    return [arr[i] for i in range(len(arr)) if i in s1], [arr[i] for i in range(len(arr)) if i not in s1]

計算量については、数字群の要素数をN、数字群全体の合計をWとすると、O(NW)となります。

Answer 2

ChatGPTの回答

[1,1,2,3,5,6,8]という自然数が格納されたリストから各要素を取り出して２つのリストに格納したい。
その結果、２つのリストの各要素の値の合計の差ができるだけ小さくなるようにしたい。
このような問題を動的計画法で解くpythonのコードを教えて欲しい。

以下は、与えられたリストを２つのリストに分割し、その２つのリストの要素の合計の差ができるだけ小さくなるようにする動的計画法のPythonコードです。このコードでは、２つのリストの要素の合計の差が最小になるようなリストの分割を求めるために、再帰関数を使用します。

def min_sum_diff(arr):
    n = len(arr)
    total_sum = sum(arr)
    
    # ２つのリストの要素の合計がsum1とsum2の場合の差を計算するためのヘルパー関数
    def subset_sum_diff(i, sum1, sum2, memo):
        if i == n:
            return abs(sum1 - sum2)
        if (i, sum1) in memo:
            return memo[(i, sum1)]
        # i番目の要素を１つ目のリストに入れる場合
        diff1 = subset_sum_diff(i+1, sum1+arr[i], sum2, memo)
        # i番目の要素を２つ目のリストに入れる場合
        diff2 = subset_sum_diff(i+1, sum1, sum2+arr[i], memo)
        memo[(i, sum1)] = min(diff1, diff2)
        return memo[(i, sum1)]
    
    # ２つのリストに分割するための再帰関数を呼び出す
    memo = {}
    min_diff = subset_sum_diff(0, 0, 0, memo)
    
    # ２つのリストを構築する
    list1 = []
    list2 = []
    i = 0
    sum1 = 0
    while i < n:
        # i番目の要素を１つ目のリストに入れる場合
        if subset_sum_diff(i+1, sum1+arr[i], total_sum-sum1-arr[i], memo) == min_diff:
            list1.append(arr[i])
            sum1 += arr[i]
        # i番目の要素を２つ目のリストに入れる場合
        else:
            list2.append(arr[i])
        i += 1
    
    return list1, list2

このコードを以下のように呼び出すことができます。

arr = [1,1,2,3,5,6,8]
list1, list2 = min_sum_diff(arr)
print("List 1:", list1)
print("List 2:", list2)

出力：

List 1: [1, 1, 2, 3, 5]
List 2: [6, 8]

この場合、２つのリストの要素の合計の差が最小となるリストの分割は、[1,1,2,3,5]と[6,8]です。

じっさいに回答コードを実行してみると

List 1: [1, 1, 2, 3, 6]
List 2: [5, 8]

ってまさか最後のコメントが間違っていたとは。
やっぱりちゃんとチェックしないと怖いな。

Comments

[actorbug]

正しい出力は、[1,1,2,3,6]と[5,8]になるはずです。

[8524ba23]

ご指摘ありがとうございます。そのとおりでした。

Answer 3

単純に降順に並べたあとに、差が小さくなる方に足していくのではダメでしょうか。

def calc(lst):
    lst = sorted(lst, reverse=True)

    grps = [[],[]]
    totals = [0,0]
    for v in lst:
        g1 = abs(totals[1] - (totals[0] + v))
        g2 = abs(totals[0] - (totals[1] + v))
        i = g1 > g2
        grps[i].append(v)
        totals[i] += v

    return grps

for lst in [[2,2,2,3,3,4,5],[4,3,2,1],[9,5,5,1]]:
    grps = calc(lst)
    print(lst, grps, abs(sum(grps[0])-sum(grps[1])))
"""
[2, 2, 2, 3, 3, 4, 5] [[5, 3, 2], [4, 3, 2, 2]] 1
[4, 3, 2, 1] [[4, 1], [3, 2]] 0
[9, 5, 5, 1] [[9, 1], [5, 5]] 0
"""

Comments

[arcxor]

そのようなナイーブな実装では最適解が得られないケースがありますね。例えば以下のケースは和を 20, 20 に分割できます。

[11, 9, 5, 5, 5, 5] [[11, 5, 5], [9, 5, 5]] 2

[8524ba23]

ああ。やっぱりダメですね。
具体例ありがとうございます。

Answer 4

def findMin(arr, i, cumsum, total):
    return abs(total - 2 * cumsum) if (i == 0) \
           else min(findMin(arr, i-1, cumsum+arr[i-1], total),
                    findMin(arr, i-1, cumsum, total))

if __name__ == "__main__":
    arr = [2, 2, 2, 3, 3, 4, 5]

    min_diff = findMin(arr, len(arr), 0, sum(arr))
    print(min_diff)

# 1

Comments

[melian]

ベストアンサーに選んでいただき、どうもありがとうございます。この場合の時間計算量(time complexity)は O(2^n) になりますので、リストの要素数が 20 程度までが限界かと思います。DP(Dynamic Programming)を利用すれば、計算量は最悪値で O(n^2) 程度に緩和できるかもしれません。

Answer 5

このコードでは、組み合わせを列挙するためにitertoolsモジュールのcombinations関数を使用しています。しかし、この方法は非常に非効率であり、数字の数が増えると計算時間が爆発的に増加します。また、remove関数を使用してリストから要素を削除することも、リストの要素数が多い場合には非常に遅くなります。

代わりに、以下のようなアルゴリズムを使用することをお勧めします。

1. 数字の合計値を計算し、その半分を目標値とします。
2. 数字を降順にソートします。
3. 数字を順番に取り出し、目標値に近づくようにグループ１とグループ２に分けます。
4. グループ１とグループ２の合計値の差を計算し、最小値を更新します。

このアルゴリズムは、数字の数に対して線形時間で動作するため、非常に効率的です。

以下は、このアルゴリズムを実装したコードです。

該当のソースコード

num = int(input())
lis = [2, 2, 2, 3, 3, 4, 5] # その他 数字群が様々あるが、、、
lis = sorted(lis, reverse=True)

total = sum(lis)
target = total // 2

sum1 = 0
sum2 = 0
for n in lis:
if sum1 < target:
sum1 += n
else:
sum2 += n

diff = abs(sum1 - sum2)
print(diff)

response:

Comments

[ikevo]

この文はダメだと思います。おそらく平均値付近の数字が複数ある時が問題かも？
4,3,2,1のように最後の方の数字が小さく微調整がきく数字の場合,[4,2][3,1]の結果となるより、[4,1][3,2]の組み合わせのほうが小さいためです。
[9,5,5,1]がわかりやすい例で、平均値付近のものが複数ある時、sum1がまだ平均以下なため５がsum1のグループになるのは政界ではないです。