🎄teratailクリスマスプレゼントキャンペーン2024🎄』開催中!

\teratail特別グッズやAmazonギフトカード最大2,000円分が当たる!/

詳細はこちら
Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Q&A

解決済

5回答

4098閲覧

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

ikevo

総合スコア5

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

0グッド

1クリップ

投稿2023/03/13 02:46

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

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

該当のソースコード

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)

試したこと

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

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

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

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答5

0

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

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

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

python

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

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

python

1def min_diff(arr): 2 s = sum(arr) // 2 3 dp = [-1] + [None] * s 4 for i in range(len(arr)): 5 for j in range(s, arr[i] - 1, -1): 6 if dp[j] is None and dp[j - arr[i]] is not None: 7 dp[j] = i 8 for p in range(s, -1, -1): 9 if dp[p] is not None: 10 break 11 s1 = set() 12 while p > 0: 13 s1.add(dp[p]) 14 p -= arr[dp[p]] 15 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)となります。

投稿2023/03/15 14:17

編集2023/03/17 21:05
actorbug

総合スコア2420

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

ChatGPTの回答

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

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

Python

1def min_sum_diff(arr): 2 n = len(arr) 3 total_sum = sum(arr) 4 5 # 2つのリストの要素の合計がsum1とsum2の場合の差を計算するためのヘルパー関数 6 def subset_sum_diff(i, sum1, sum2, memo): 7 if i == n: 8 return abs(sum1 - sum2) 9 if (i, sum1) in memo: 10 return memo[(i, sum1)] 11 # i番目の要素を1つ目のリストに入れる場合 12 diff1 = subset_sum_diff(i+1, sum1+arr[i], sum2, memo) 13 # i番目の要素を2つ目のリストに入れる場合 14 diff2 = subset_sum_diff(i+1, sum1, sum2+arr[i], memo) 15 memo[(i, sum1)] = min(diff1, diff2) 16 return memo[(i, sum1)] 17 18 # 2つのリストに分割するための再帰関数を呼び出す 19 memo = {} 20 min_diff = subset_sum_diff(0, 0, 0, memo) 21 22 # 2つのリストを構築する 23 list1 = [] 24 list2 = [] 25 i = 0 26 sum1 = 0 27 while i < n: 28 # i番目の要素を1つ目のリストに入れる場合 29 if subset_sum_diff(i+1, sum1+arr[i], total_sum-sum1-arr[i], memo) == min_diff: 30 list1.append(arr[i]) 31 sum1 += arr[i] 32 # i番目の要素を2つ目のリストに入れる場合 33 else: 34 list2.append(arr[i]) 35 i += 1 36 37 return list1, list2

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

Python

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

出力:

Python

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

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

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

Python

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

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

投稿2023/03/13 07:46

編集2023/03/16 00:56
can110

総合スコア38341

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

actorbug

2023/03/15 14:19

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

2023/03/16 00:56

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

0

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

Python

1def calc(lst): 2 lst = sorted(lst, reverse=True) 3 4 grps = [[],[]] 5 totals = [0,0] 6 for v in lst: 7 g1 = abs(totals[1] - (totals[0] + v)) 8 g2 = abs(totals[0] - (totals[1] + v)) 9 i = g1 > g2 10 grps[i].append(v) 11 totals[i] += v 12 13 return grps 14 15for lst in [[2,2,2,3,3,4,5],[4,3,2,1],[9,5,5,1]]: 16 grps = calc(lst) 17 print(lst, grps, abs(sum(grps[0])-sum(grps[1]))) 18""" 19[2, 2, 2, 3, 3, 4, 5] [[5, 3, 2], [4, 3, 2, 2]] 1 20[4, 3, 2, 1] [[4, 1], [3, 2]] 0 21[9, 5, 5, 1] [[9, 1], [5, 5]] 0 22"""

投稿2023/03/13 05:22

can110

総合スコア38341

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

arcxor

2023/03/13 07:25

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

2023/03/13 07:33

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

0

ベストアンサー

python

1def findMin(arr, i, cumsum, total): 2 return abs(total - 2 * cumsum) if (i == 0) \ 3 else min(findMin(arr, i-1, cumsum+arr[i-1], total), 4 findMin(arr, i-1, cumsum, total)) 5 6if __name__ == "__main__": 7 arr = [2, 2, 2, 3, 3, 4, 5] 8 9 min_diff = findMin(arr, len(arr), 0, sum(arr)) 10 print(min_diff) 11 12# 1

投稿2023/03/13 04:03

melian

総合スコア20592

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

melian

2023/03/13 05:31 編集

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

0

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

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

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

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

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

該当のソースコード

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:

投稿2023/03/13 03:06

NCsn

総合スコア15

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

ikevo

2023/03/13 04:17

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.36%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問