質問をすることでしか得られない、回答やアドバイスがある。

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

ただいまの
回答率

87.37%

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

解決済

回答 1

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 1,167
退会済みユーザー

退会済みユーザー

今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も必要ですよね

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

checkベストアンサー

0

例えば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書かないので自信がないですが、こんな感じのコードになります。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

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

  • ただいまの回答率 87.37%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る