ログイン
編集不可のページディスカッション情報添付ファイル
akky/cp/partial-sum

MMA

問題

部分和問題

概要

n個の整数からいくつか選びその和をkにすることができるか判定せよ

制約

n = 1..20
a_i = -1e8..1e8
k = -1e8..1e8

入力形式

n k
a_1 a_2 a_3 ...... a_n

  • 例1
4 13
1 2 4 7
Yes
  • 例2
3 15
1 2 4 7
No

コード

深さ優先探索

n, k = map(int, input().split())
a = [int(e) for e in input().split()]

def dfs(i, _sum):
    # decide n nums if add or not
    if i == n:
        # all nums were decided
        return _sum == k
    if(dfs(i + 1, _sum)):
        # not add ith num
        return True
    if(dfs(i + 1, _sum + a[i])):
        # add ith num
        return True
    return False

if(dfs(0, 0)):
    print("Yes")
else:
    print("No")

ビット全探索

n, k = map(int, input().split())
a = [int(e) for e in input().split()]

for bit in range(1<<n):
    _sum = 0
    for i in range(n):
        if bit & 1<<i:
            _sum += a[i]
    if _sum == k:
        print("Yes")
        exit()

print("No")

itertoolsの利用

from itertools import combinations
n, k = map(int, input().split())
a = [int(e) for e in input().split()]

for i in range(1, n+1):
    for c in combinations(a, i):
        if sum(c) == k:
            print("Yes")
            exit()

print("No")

DP

n, k = map(int, input().split())
a = [int(e) for e in input().split()]

dp = [[False] * (k+1) for _ in range(n+1)]
dp[0][0] = True

for i in range(n):
    for j in range(k+1):
        if j >= a[i]:
            dp[i+1][j] = dp[i][j - a[i]] or dp[i][j]
        else:
            dp[i+1][j] = dp[i][j]

if dp[n][k]:
    print("Yes")
else:
    print("No")

要点

  • 各数を足す場合と足さない場合を分けて全探索
  • 計算量は状態数を考えてO(2^n)
  • 再帰関数の計算量は状態数を考える
  • DPを利用すれば計算量はO(n*k)

出典

プログラミングコンテストチャレンジブック第2版 p34

参考

akky/cp/partial-sum (最終更新日時 2018-12-24 00:21:09 更新者 akky)