回答編集履歴
2
実際の組み合わせを求めるコード追加
test
CHANGED
|
@@ -1,7 +1,7 @@
|
|
|
1
|
-
グループ1とグループ2に分けたときに、合計値の差が最も小さくなる分け方を求めるという問題ですが、
|
|
1
|
+
グループ1とグループ2に分けたときに、合計値の差が最も小さくなる分け方を求めるという問題ですが、仮に合計の小さい方をグループ1とすることにすると、グループ1の合計は全体の合計の半分以下となります。
|
|
2
|
-
グループ1の選び方に注目すると、「全体の合計の半分以下の範囲で、グループ1の合計を最大いくつにすることができるか」という問題に帰着できます。
|
|
2
|
+
ここで、グループ1の選び方に注目すると、「全体の合計の半分以下の範囲で、グループ1の合計を最大いくつにすることができるか」という問題に帰着できます。
|
|
3
3
|
|
|
4
|
-
こ
|
|
4
|
+
この問題は、「目標値が全体の合計の半分である部分和問題を動的計画法で解いて、解く際に使用したテーブルから、目標値以下で作成可能な最大の部分和を求める」という手順で解くことができます。
|
|
5
5
|
|
|
6
6
|
こちらの方針で解いたものが、以下のコードになります。
|
|
7
7
|
```python
|
|
@@ -15,3 +15,23 @@
|
|
|
15
15
|
if dp[p]:
|
|
16
16
|
return sum(arr) - 2 * p
|
|
17
17
|
```
|
|
18
|
+
|
|
19
|
+
実際の組み合わせを求めたい場合は、以下のようになります。
|
|
20
|
+
```python
|
|
21
|
+
def min_diff(arr):
|
|
22
|
+
s = sum(arr) // 2
|
|
23
|
+
dp = [-1] + [None] * s
|
|
24
|
+
for i in range(len(arr)):
|
|
25
|
+
for j in range(s, arr[i] - 1, -1):
|
|
26
|
+
if dp[j] is None and dp[j - arr[i]] is not None:
|
|
27
|
+
dp[j] = i
|
|
28
|
+
for p in range(s, -1, -1):
|
|
29
|
+
if dp[p] is not None:
|
|
30
|
+
break
|
|
31
|
+
s1 = set()
|
|
32
|
+
while p > 0:
|
|
33
|
+
s1.add(dp[p])
|
|
34
|
+
p -= arr[dp[p]]
|
|
35
|
+
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]
|
|
36
|
+
```
|
|
37
|
+
計算量については、数字群の要素数をN、数字群全体の合計をWとすると、O(NW)となります。
|
1
コードを少し短縮
test
CHANGED
|
@@ -10,8 +10,7 @@
|
|
|
10
10
|
dp = [True] + [False] * s
|
|
11
11
|
for i in range(len(arr)):
|
|
12
12
|
for j in range(s, arr[i] - 1, -1):
|
|
13
|
-
|
|
13
|
+
dp[j] = dp[j] or dp[j - arr[i]]
|
|
14
|
-
dp[j] = True
|
|
15
14
|
for p in range(s, -1, -1):
|
|
16
15
|
if dp[p]:
|
|
17
16
|
return sum(arr) - 2 * p
|