両腕秤(DFS)

深度/幅優先ナビゲーション(DFS、BFS)による

に質問

両腕秤（DFS）

異なる重量のK個のテーパと空きボウルがあります.すべてのピボット重量は整数で、ボウル重量はゼロです.一度両腕秤で欲しい水の重さをボウルに盛り付けたいです.
与えられたすべての重量の和はSである.例えば、3個を添加し、各ピボットの重量が{1,2,6}である場合、S=9は、両腕秤を1回使用するだけで、1~Sの間の対応するすべての重量の水を以下のようにボウルに入れることができる.Xはボウルに盛られた水の重さを表し、汚れたボウルも表します.

コーンの重量が{1、5、7}である場合、S=13、ボウルに盛ることができる水の重量は{1、2、3、4、5、6、7、8、11、12、13}であり、1からSまでの重量は9と10に対応する重量の水を盛ることができない.
K(3<=K<=13)個のピボット重量が与えられている場合は、1~Sの間の整数のうち、測定不可能な水の重量がどれだけあるかを出力するプログラムを作成します.
■説明の入力
第1行は自然数K(3<=K<=13)を与える.
2行目では、各Kピボットの重量はスペースの間にあります.各椎骨の重量は1〜200000である.
■出力説明
最初に測定できない指数を出力してください.
■入力例1
3
1 5 7
■出力例1
2

コード#コード#💻

に答える

import sys
#sys.stdin = open("input.txt", "rt")        # read text

def DFS(L, sum):
    global res
    if L == n:
        if 0 < sum <= s:
            res.add(sum)
    else:
        DFS(L+1, sum+G[L])                  # 추를 왼쪽에 놓는다.
        DFS(L+1, sum-G[L])                  # 추를 오른쪽에 놓는다.
        DFS(L+1, sum)                       # 추를 놓지 않는다.

if __name__ == "__main__":
    n = int(input())
    G = list(map(int, input().split()))
    s = sum(G)
    res = set()                             # 중복 제거
    DFS(0, 0)
    print(s-len(res))

リファレンス

インフラストラクチャ:Pythonアルゴリズム回答