NがPythonのセット{A、B}から選択された整数の合計として表現できるかどうかを確認します

数のターゲットがあるとします。 AとBの2つの数字があります。AとBを何度でも追加して、ターゲットを取得できるかどうかを確認する必要があります。

したがって、入力がTarget =26 A =5 B =7の場合、出力はTrueになります。これは、（7 + 7 + 7 + 5）のようにAとBを追加することで26を取得できるためです。

これを解決するには、次の手順に従います-

• 関数util（）を定義します。これには、x、a、b、is_ok、targetが必要です
• x>ターゲットの場合、
  • 戻る
• is_ok [x]がTrueの場合、
  • 戻る
• is_ok [x]：=True
• util（x + a、a、b、is_ok、target）
• util（x + b、a、b、is_ok、target）
• メインの方法から次のようにします-
• is_ok：=サイズの配列（ターゲット+ 1）で、Falseで埋めます
• util（0、a、b、is_ok、target）
• return is_ok [target]

例

理解を深めるために、次の実装を見てみましょう-

def util(x, a, b, is_ok, target):
   if x > target:
      return
   if is_ok[x]:
      return
   is_ok[x] = True
   util(x + a, a, b, is_ok, target)
   util(x + b, a, b, is_ok, target)
def solve(target, a, b):
   is_ok = [False] * (target + 1)
   util(0, a, b, is_ok, target)
   return is_ok[target]
target = 26
A = 5
B = 7
print(solve(target, A, B))

入力

26, 5, 7

出力

True