Loading Cargo の続き
ヒントに書いてあった「パーティション問題(Partition problems)」を調べてみた。
がんばって、Partition problem (Wikipedia 英語版) を読んでみたが、よくわからない。( ´Д`;)
最初に The pseudo-polynomial algorithm というのが載っていて、C#のコードがあったので、とりあえず、それをPythonに移植してみる。
ちなみに、pseudo-polynomialとは準多項式だそうだ。準多項式とは、多項式を一般化したものである、って全然意味分からんのでスルー。
The pseudo-polynomial algorithm
C#のコードを移植したのがこちら。
重量差を求めるコードではなく、荷物をきれいに2等分できるかどうか調べるだけのようだ。
def find_partition(data): n = len(data) total = sum(data) # 横 n+1、縦 total//2+1 の2次元配列を作成 p = [[False for _ in range(n + 1)] for _ in range(total // 2 + 1)] # Pの初期化(Pの一番上の行だけをTrueにする) for i in range(n + 1): p[0][i] = True # P(i,j) に P(i,j-1) or P(i-s[j-1],j-1) をセットしていく for i in range(1, total // 2 + 1): for j in range(1, n + 1): if data[j - 1] <= i: # i-data[j-1] >= 0 p[i][j] = p[i][j - 1] or p[i - data[j - 1]][j - 1] else: p[i][j] = p[i][j - 1] # Pの右下がTrueなら、荷物はきれいに2等分できる return p[total // 2][n]
何をやってるのかというと、
- 横(n+1)、縦(total//2+1) で boolの2次元配列 P を作成する。nは荷物の数、totalは全荷物の重さ合計。
- Pを初期化。一番上の行だけTrueにする。
- P(i,j) に P(i,j-1) or P(i-s[j-1],j-1) をセットしていく。(後述)
2次元配列 P を作成すると、荷物からn個取り出して、重さxを作成できるかどうかがわかるようになる。例えば、荷物が {3,1,2} のとき、Pは、下のような2次元配列となる。
i \ j | {} | {3} | {3,1} | {3,1,2} |
---|---|---|---|---|
0 | True | True | True | True |
1 | False | False | True | True |
2 | False | False | False | True |
3 | False | True | True | True |
縦軸(i)が重さ、横軸(j)が荷物の集合となっていて、bool値は「jからn個の荷物を取り出して、重さiを作成できるかどうか」を示している。例えば、上の表からは
- {3}からn個を取り出して、重さ 0,3 は作成できるが、重さ 1,2 は作成できない。
- {3,1}からn個を取り出して、重さ 0,1,3 は作成できるが、重さ 2 は作成できない。
- {3,1,2}からn個を取り出して、重さ 0,1,2,3 を作成できる。
ということがわかる。
一番右下のマスからは、
- {3,1,2}からn個を取り出して、重さ 3 を作成できる。
ことがわかる。重さ 3 とは、総重量の半分なので、つまり、この場合は、荷物{3,1,2}を、きれいに2等分できることがわかるのだ。
Pの作成
どうやってこの表を作成しているかというと、手順3の
- P(i,j) に P(i,j-1) or P(i-s[j-1],j-1) をセットしていく。
がポイントとなる。
まず、P(i,j-1) がTrueなら、P(i,j)がTrueになる。
{a,b}で重さxを作成できるのなら、{a,b,c}で重さxを作成できるのは当然だからだ。
もう一つ、P(i-s[j-1],j-1) がTrueなら、P(i,j)がTrueになる。
s[j-1]とは、新たに追加された荷物のことで、例えば、{3,1}なら1、{3,1,2}なら2となる。
{a,b}で重さxを作成できるなら、{a,b,c}で重さx+cは作成できるというわけだ。
これを左上から右下に向かって作成していくと、表が完成するという仕組み。
差の最小値を求める
上のコードは、きれいに2等分できるかどうかを調べるものだったが、今回の問題は、2つのグループの差の最小値を求めるわけだから、もう少し追加する必要がある。
この表の最右列を見ると、すべての荷物からn個取り出して、重さxを作成できるかどうかがわかる。総重量の半分が作成できなくても、できるだけ近い重さを作成すればいいわけだから、最右列の一番下にあるTrueを探せばいいことがわかる。
# 最右列で、一番下にあるTrueの行番号(i)を探す max_i = max(i for i in range(total // 2 + 1) if p[i][n]) # total-i*2 が差の最小値となる return total - max_i * 2
まとめたのがこちら
def checkio(data): n = len(data) total = sum(data) # 横 n+1、縦 total//2+1 の2次元配列を作成 p = [[False for _ in range(n + 1)] for _ in range(total // 2 + 1)] # Pの初期化(Pの一番上の行だけをTrueにする) for i in range(n + 1): p[0][i] = True # P(i,j) に P(i,j-1) or P(i-s[j-1],j-1) をセットしていく for i in range(1, total // 2 + 1): for j in range(1, n + 1): if data[j - 1] <= i: # i-data[j-1] >= 0 p[i][j] = p[i][j - 1] or p[i - data[j - 1]][j - 1] else: p[i][j] = p[i][j - 1] # 最右列で、一番下にあるTrueの行番号(i)を探す max_i = max(i for i in range(total // 2 + 1) if p[i][n]) # total-i*2 が差の最小値となる return total - max_i * 2
無事にクリア。まだ半分ぐらいしか理解していないけども。
よりシンプルに
さらにあれこれ調べてみた。どうやら「Balanced Partition」というキーワードでググるといいようだ。
こちらのサイトにも、同じ問題で C++のコードが載っていた。これをPythonで書き直してみる。
https://sites.google.com/site/aligoeren/algorithms-r/balanced-partition-problem
基本的な部分は同じだが、先ほどよりもシンプルに解いている。最大のポイントは、2次元配列ではなく1次元配列を使っていること。どうせ最右列しか使わないんだから、1次元配列を上書きしながら更新しているわけだ。
元のコードにいくつか変更を加えている。
- iとjがWikipediaの説明と逆だったので、iとjを入れ替えた。
- 配列が (total+1)サイズになっていたが、(total//2+1)サイズで十分なので短くした。
- 総重量の半分との差=diff となっていたが、今回の問題にあわせ、グループの重量差=diff とした。
- グループの重さをansとして求めていたが、今回の問題では不要なので削除した。
コードはこちら
def checkio(data): total = sum(data) p = [True] + [False] * (total // 2) diff = total for j in range(len(data)): for i in range(len(p) - 1, data[j] - 1, -1): p[i] = p[i] or p[i - data[j]] if p[i]: diff = min(diff, abs(total - i * 2)) return diff
http://www.checkio.org/mission/loading-cargo/publications/natsuki/python-3/third/
とてもシンプル。これはClearカテゴリで公開しておこう。