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カテゴリで公開しておこう。

summer_tree_home

Check iOでPython3をマスターするぜっ