[python3][アルゴリズム] DPの部分和で詰まってしまった

Question

今DPを勉強中で、AtCoderというサイトでいろいろ問題を解いています

この問題で詰まりました
http://atcoder.jp/contests/abc047/tasks/abc047_a

これ自体は簡単なのですが
子供の数がX人、パックの数がN個になった時にどうなるかと考えてみて、
X >= 3のときにアルゴリズムはわかるが実際にどう書いたら良いか分からなくなりました。

例えばX = 3なら、パックの部分和のキャンディが全部のキャンディの1/3になる組み合わせがあれば
その組み合わせをパックのリストから除外して残ったリストからまたパックの同じように部分和を考えればいいと思います。

X > 3についてもloopを使えばできると思うのですが、具体的にどう書けば良いのでしょうか

###問題自体の解答はこれです
dp[i+1][j] : i番目までのパックからいくつか選んで中のキャンディの総和が全部のキャンディの半分(この問題では子供が二人なので)になるようにすることが可能かどうかの論理知。

dp[i][j]がTrueならdp[i+1][j]もTrue
dp[i][j]がFalseのとき、(j >= packs[i]の場合のみ)dp[i][j-packs[i]]をみてTrueならdp[i+1][j]もTrue

参考: https://qiita.com/drken/items/a5e6fe22863b7992efdb#%E5%95%8F%E9%A1%8C-3%E9%83%A8%E5%88%86%E5%92%8C%E5%95%8F%E9%A1%8C

packs = [int(candies) for candies in input().split()]
N = int(len(packs))
X = 2
if sum(packs) % X == 0:
    A = int(sum(packs) / X) # 部分和がAになれば良い
else: 
    print('No')
    exit()

dp = [[False] * (A + 1)] * (N + 1)
dp[0][0] = True

for i in range(N):
    for j in range(A+1):
        if dp[i][j]:
            dp[i+1][j] = dp[i][j]
        elif j >= packs[i]:
            dp[i+1][j] = dp[i][j - packs[i]]

if dp[N][A]:
    ans = "Yes"
else:
    ans = "No"

print(ans)

追記

i, j に加えて現在のリストの情報kも必要ですよね

Answer 1

例えばX = 3なら、パックの部分和のキャンディが全部のキャンディの1/3になる組み合わせがあれば
その組み合わせをパックのリストから除外して残ったリストからまたパックの同じように部分和を考えればいいと思います。

この考えをベースにする場合、現在使われてるパックの状態をdp配列に持たせる必要があります。
例えば整数kの二進数表記を使っているパック集合を表すとすれば、もはや何番目のパックまで調べたかを表すiは不要になりますし、現在使われているキャンディの総和jも不要になります。
(補足すると、同じパックを重複して使うようなことがないように気を付けさえすれば元の問題でもiは不要で、使われてるパックが分かれば現在使われてるキャンディの総和を計算することができるので、i,jともに不要になります。)

あとは dp[k] を何を表す配列とするかですが、

sum(k) := 集合kに含まれるキャンディの総和
Qk := sum(k) // A    #あまり切り捨て
Rk := sum(k) % A

としたとき

dp[k] := 集合kのパックを全て使って、Qk人にA個ずつ配り、Rk個余るような組み合わせが存在するならTrue、そうでなければFalse

とすることで

i := k に含まれないパック
k|i := k に i を追加した集合
C[i] := パックiのキャンディの個数
dp[k] := (Qk == Qk|i or Rk + C[i] == A)がいずれかのiについてTrue

と遷移できます。

X = int(input())
packs = [int(candies) for candies in input().split()]
N = int(len(packs))
if sum(packs) % X == 0:
    A = int(sum(packs) / X) # 部分和がAになれば良い
else: 
    print('No')
    exit()
#集合ごとのキャンディの合計
packSum = [sum([packs[x] for x in range(N) if i & (1 << x) != 0]) for i in range(1 << N)]
dp = [False] * (1 << N)
dp[0] = True #どのパックも使わないとき条件を満たす
for i in range(len(dp)): #現在使われてるパックの集合
    if not dp[i]:
        continue
    for j in range(N): #追加するパックの候補
        if i & (1 << j) == 0: #すでに使われていないか調べる
            dp[i | (1 << j)] = dp[i | (1 << j)] or packSum[i] // A == packSum[i | (1 << j)] // A or packSum[i] % A + packs[j] == A
            

if dp[-1]:
    ans = "Yes"
else:
    ans = "No"

print(ans)

普段Python書かないので自信がないですが、こんな感じのコードになります。