[DFS]両腕秤
両腕秤（DFS）
異なる重量のK個のテーパと空きボウルがあります.各ピボットの重量は整数で、器の重量は0です.
とみなす一度両腕秤で欲しい水の重さをボウルに盛り付けたいです.
与えられたすべての重量の和はSである.たとえば、ピボットあたり3個の重量を追加
面、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
に答える
def dfs(a, b):
if a == k:
if 1 <= b <= s and check[b] == 0:
lst.append(b)
check[b] = 1
else:
dfs(a + 1, b + w[a])
dfs(a + 1, b - w[a])
dfs(a + 1, b)
k = int(input())
w = list(map(int, input().split()))
s = sum(w)
lst = []
check = [0] * (s + 1)
dfs(0, 0)
print(s - len(lst))
def dfs(a, b):
if a == k:
if 1 <= b <= s and check[b] == 0:
lst.append(b)
check[b] = 1
else:
dfs(a + 1, b + w[a])
dfs(a + 1, b - w[a])
dfs(a + 1, b)
k = int(input())
w = list(map(int, input().split()))
s = sum(w)
lst = []
check = [0] * (s + 1)
dfs(0, 0)
print(s - len(lst))コードをこの3つのタイプに分けます.その後、lstに値を追加する方法で値を作成し、チェックリストに再挿入できません.
しかし、この方法よりもっと良い方法があります.
def dfs(a, b):
if a == k:
if 1 <= b <= s:
nums.add(b)
else:
dfs(a + 1, b + w[a])
dfs(a + 1, b - w[a])
dfs(a + 1, b)
k = int(input())
w = list(map(int, input().split()))
s = sum(w)
nums = set()
check = [0] * (s + 1)
dfs(0, 0)
print(s - len(nums))これがsetを使用する方法です.setは重複する値を作成しないので、無条件に挿入されます.
むしろ前の方法よりこの方法の方がいいです
Reference
この問題について([DFS]両腕秤), 我々は、より多くの情報をここで見つけました https://velog.io/@sparkbosing/DFS-양팔저울テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol