NetworkX④(最大流問題)

NetworkXを、使って 最大流問題 を解いてみます。

最大流問題

グラフ間に流れる数値を最大化させる問題を 最大流問題 といいます。

[最大流問題の例]

ネットワーク上の2台のコンピュータs、tがありsからtにデータを送ります。

このネットワークには全部でN台のコンピュータがあり、いくつかのコンピュータ間は一方向性の

通信ケーブルで接続されていて、それぞれ1秒間に通信できる最大のデータ量が決まってきます。

sからtへ1秒間で最大どれだけのデータを送信することができるでしょうか。

この問題に対応するネットワーク上の 各コンピュータデータ量 を下記のグラフで表示します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import networkx as nx

G = nx.DiGraph()

#(始点,終点,重み)でエッジを設定
G.add_edges_from([('s', '1', dict(capacity=10)),
('s', '2', dict(capacity=2)),
('1', '2', dict(capacity=6)),
('1', '3', dict(capacity=6)),
('3', '2', dict(capacity=3)),
('2', 't', dict(capacity=5)),
('3', 't', dict(capacity=8)),
])

#エッジラベルの描画時に'capacity'の表示を無くすための工夫
edge_labels = {(i, j): w['capacity'] for i, j, w in G.edges(data=True)}
pos = nx.spring_layout(G, k=10)
nx.draw_networkx_edge_labels(G,pos, edge_labels=edge_labels)

# グラフの描画
nx.draw_networkx(G, pos)

[実行結果]

解法

最大流問題 を解くためには、maximum_flow関数 を使います。

引数には、グラフオブジェクト始点ノード終了ノード を設定します。

[Google Colaboratory]

1
2
3
4
5
6
7
flow_value, flows = nx.maximum_flow(G, 's', 't')
print(f'maximum flow: {flow_value}')

caps = nx.get_edge_attributes(G, 'capacity')
for u in nx.topological_sort(G):
for v, flow in sorted(flows[u].items()):
print(f' ({u}, {v}): {flow}/{caps[(u, v)]}')

[実行結果]

maximum flow: 11

  (s, 1): 9/10

  (s, 2): 2/2

  (1, 2): 3/6

  (1, 3): 6/6

  (3, 2): 0/3

  (3, t): 6/8

  (2, t): 5/5

sからtへの最大流は 11 と導き出すことができました。

また、最大流が流れる際に 各ノード間に流すデータ通信 も表示しています。

NetworkX③(パス/閉路/放射状の描画)

NetworkX を使っていろいろなタイプのグラフを描画してみます。

パス

まずは パス を描画します。

add_path関数 に複数のノード番号を設定します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
import networkx as nx

G = nx.DiGraph() # 有向グラフ (Directed Graph)

# 指定したパス上の頂点と辺を追加
nx.add_path(G, [1, 2, 3, 4, 5]) # 1 → 2 → 3 → 4 → 5

nx.draw_networkx(G)

[実行結果]

順番に ノードを辿ったグラフ が描画されました。

閉路

次に 閉路 を描画します。

add_cycle関数 に複数のノード番号を設定します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
import networkx as nx

G = nx.DiGraph() # 有向グラフ (Directed Graph)

# 指定した閉路上の頂点と辺を追加
nx.add_cycle(G, [1, 2, 3, 4, 5]) # 1 → 2 → 3 → 4 → 5 → 1

nx.draw_networkx(G)

[実行結果]

順番にノード番号を辿り、最後のノードから最初の番号に戻る 閉路グラフ を描画することができました。

放射状

最後に 放射状 のグラフを描画します。

add_star関数 に複数のノード番号を設定します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
import networkx as nx

G = nx.DiGraph() # 有向グラフ (Directed Graph)

# 放射状に頂点と辺を追加
nx.add_star(G, [1, 2, 3, 4, 5]) # 1 → 2, 1 → 3, 1 → 4, 1 → 5

nx.draw_networkx(G)

[実行結果]

最初のノードから、2番目以降のノード全てにエッジ(辺)のある 放射状のグラフ を描画することができました。

NetworkX②(ノード削除、エッジ削除)

ノード削除

今回はグラフから ノードを削除 してみます。

まずは、前回記事と同様のグラフを描画します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
import networkx as nx

G = nx.DiGraph() # 有向グラフ (Directed Graph)

# 頂点の追加
G.add_node(1)
G.add_nodes_from([3, 4, 5])

# 辺の追加 (頂点も必要に応じて追加されます)
G.add_edge(1, 2)
G.add_edges_from([(1, 3), (2, 5), (3, 4), (4, 5)])

nx.draw_networkx(G)

[実行結果]

上記のグラフから、ノード(頂点)を削除 してみます。

[Google Colaboratory]

1
2
3
# 頂点の削除 (削除された頂点に接続されている辺も削除されます)
G.remove_node(5) # 頂点を1つ削除
G.remove_nodes_from([3, 4]) # 頂点を複数削除

[実行結果]

ノードが削除されました。

また削除されたノードに関係する エッジも削除 されていることが確認できます。

エッジ削除

今度はグラフから エッジを削除 してみます。

まずグラフ図を描画します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
import networkx as nx

G = nx.DiGraph() # 有向グラフ (Directed Graph)

# 頂点の追加
G.add_node(1)
G.add_nodes_from([3, 4, 5])

# 辺の追加 (頂点も必要に応じて追加されます)
G.add_edge(1, 2)
G.add_edges_from([(1, 3), (2, 5), (3, 4), (4, 5)])

nx.draw_networkx(G)

[実行結果]

上記のグラフから、エッジ(辺)を削除 してみます。

[Google Colaboratory]

1
2
3
# 辺の削除
G.remove_edge(3, 4) # 辺を1つ削除
G.remove_edges_from([(1, 3), (2, 5)]) # 辺を複数削除

[実行結果]

エッジ(辺)が削除されました。

ノードの削除とは違い、削除されたエッジに合わせてノードが削除されることはないようです。

NetworkX ①(グラフ描画)

NetworkX

NetworkX は、グラフ理論ネットワーク理論系の計算 を行うためのPythonパッケージです。

簡単にグラフが定義できたり,図を作ったりできます。

グラフは 頂点(ノード)辺(エッジ) で成り立っています。

無向グラフ

辺に向きがないグラフを 無向グラフ といいます。

NetworkX を使って 無向グラフ を描いてみます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
import networkx as nx

G = nx.Graph() # 無向グラフ

# 頂点の追加
G.add_node(1)
G.add_nodes_from([3, 4, 5])

# 辺の追加 (頂点も必要に応じて追加されます)
G.add_edge(1, 2)
G.add_edges_from([(1, 3), (2, 5), (3, 4), (4, 5)])

nx.draw_networkx(G)

[実行結果]

辺(エッジ)に矢印のない 無向グラフ を表示することができました。

有向グラフ

辺に向きがあるグラフを 有向グラフ といいます。

NetworkX を使って 有向グラフ を描いてみます。(3行目だけが変更されています)

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
import networkx as nx

G = nx.DiGraph() # 有向グラフ (Directed Graph)

# 頂点の追加
G.add_node(1)
G.add_nodes_from([3, 4, 5])

# 辺の追加 (頂点も必要に応じて追加されます)
G.add_edge(1, 2)
G.add_edges_from([(1, 3), (2, 5), (3, 4), (4, 5)])

nx.draw_networkx(G)

[実行結果]

辺(エッジ)に矢印のある 有向グラフ を表示することができました。

Union Find木を使って問題を解く②

Union Find木を使って問題を解く②

前前回記事で実装した Union Find木 を使って、下記の問題を解いてみます。

[問題]

N匹の動物がいて、1,2、・・・・Nと番号がつけられています。

動物はすべて3つの種類A,B,Cのいずれかです。

AはBと食べ、BはCを食べ、CはAを食べます。

そして次の2種類の情報が順番に与えられます。

 ・タイプ1:xとyは同じ種類です。

 ・タイプ2:xはyを食べます。

これらの情報はすべて 正しいとは限りません。

以前に与えられた情報と 矛盾する情報 や、x、yが正しい番号でない ような
間違った情報が与えられる可能性があります。

与えられた情報のうち、間違った情報の個数 を出力してください。

また間違った情報は捨てると考えます。

[条件]

・動物数 は、1以上 50000以下

・与えられる情報の数は、0以上 100000以下

[解き方]
Union Find木 は、同じグループを管理するデータ構造ですが、この問題では同じ情報だけではなく 食べる という関係があります。

各動物について3つの要素 i-A、i-B、i-C をつくり、3×N個の要素で Union Find木 を作成し、次のように考えます。

  • i-xiが種類xである場合 を表す。
  • 各グループは、それらが すべて同時に起こる ことが分かっている。

例えば、i-Aj-B が同じグループである場合、iが種類Aならばjは必ず種類Bであり、jが種類Bならばiはかならず種類Aである ことを表します。

そうするとそれぞれの情報について、以下を行えばよいことになります。

  • タイプ1:xとyが同じ種類の場合
    x-Aとy-Ax-Bとy-Bx-Cとy-Cの3つのペアをグループ化する。
  • タイプ2:xがyを食べる場合
    x-Aとy-Bx-Bとy-Cx-Cとy-Aの3つのペアをグループ化する。

また、それぞれグループ化する前に 矛盾がおきているかどうか のチェックを行います。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#-------------入力---------------
n = 100 # 動物の数
# 2種類のタイプ情報、動物1、動物2
info_lst = [{'type':1, 'x':101, 'y':1},
{'type':2, 'x':1, 'y':2},
{'type':2, 'x':2, 'y':3},
{'type':2, 'x':3, 'y':3},
{'type':1, 'x':1, 'y':3},
{'type':2, 'x':3, 'y':1},
{'type':1, 'x':5, 'y':5}]
#--------------------------------
uf = UnionFind(n * 3)
ans = 0

for info in info_lst:
tp = info['type']
# [1 ~ n ]の範囲を、[0 ~ n - 1 ]の範囲にする
x, y = info['x'] - 1, info['y'] - 1

# 動物の番号の範囲をチェック
if x < 0 or x >= n or y < 0 or y >= n:
print('動物番号の範囲チェックエラー', info)
ans += 1
else:
if tp == 1: # 同じ種類の場合
if uf.same(x, y + n) or uf.same(x, y + n * 2):
print('矛盾', info)
ans += 1
else:
print('同じ種類としてグループ化', info)
uf.union(x, y)
uf.union(x + n, y + n)
uf.union(x + n * 2, y + n * 2)
else: # xはyを食べる場合
if uf.same(x, y) or uf.same(x, y + n * 2):
print('矛盾', info)
ans += 1
else:
print('食べられる種類としてグループ化', info)
uf.union(x, y + n)
uf.union(x + n, y + n * 2)
uf.union(x + n * 2, y)
print()
print('答え', ans)

[実行結果]

動物番号の範囲チェックエラー {'type': 1, 'x': 101, 'y': 1}

食べられる種類としてグループ化 {'type': 2, 'x': 1, 'y': 2}

食べられる種類としてグループ化 {'type': 2, 'x': 2, 'y': 3}

矛盾 {'type': 2, 'x': 3, 'y': 3}

矛盾 {'type': 1, 'x': 1, 'y': 3}

食べられる種類としてグループ化 {'type': 2, 'x': 3, 'y': 1}

同じ種類としてグループ化 {'type': 1, 'x': 5, 'y': 5}


答え 3

1つめの情報は 番号として間違っていて、4つめと5つめの情報は 矛盾している ので、正解は3 ということになります。

Union Find木を使って問題を解く

Union Find木を使って問題を解く

前回記事で実装した Union Find木 を使って、下記の問題を解いてみます。

[問題]

人 1 から 人 N までのN 人の人がいます。

「人Ai と人 Bi は友達である」という情報が M 個与えられます。

同じ情報が複数回与えられることもあります。

X と Y が友達、かつ、Y と Z が友達ならば、X と Z も友達です。

また、M 個の情報から導くことができない友達関係は存在しません。

いじわるな高橋君は、このN人をいくつかのグループに分け、全ての人について

「同じグループの中に友達がいない」という状況を作ろうとしています。

最小でいくつのグループに分ければ良いでしょうか?

[条件]

・人数Nは、2以上 200000以下です。

・友達関係の数Mは、0以上 200000以下です。

・AiとBiは、1以上 N以下です。

・AiとBiは、異なる数字です。

[解き方]
Union Find木 を使って友達同士のグループを作ります。

同じグループの中に友達がいない 状況を作るためには、友達の数が一番多いグループの人数分だけ グループをつくればいいことになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#-----------入力1---------------
n = 5 # 人数
lst = [(1, 2), (3, 4), (5, 1)] # 友達関係
#-----------入力2---------------
# n = 4 # 人数
# lst = [(1, 2), (2, 1), (1, 2), (2, 1), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)] # 友達関係
#-----------入力3---------------
#n = 10 # 人数
#lst = [(3, 1), (4, 1), (5, 9), (2, 6)] # 友達関係
#--------------------------------
uf = UnionFind(n) # 前回記事で実装した「Union Find木」を使う

for l in lst: # 友達関係から
uf.union(l[0]-1, l[1]-1) # 1からNを、0からN-1に変換しながら、友達グループを作成

ans = 0 # 友達がいない状況をつくるためのグループ数
for g in uf.all_group_members().values(): # 友達グループごとにループ
print(f'友達グループ', g) # 友達グループのメンバー
# 友達の数が「友達がいない状況をつくるためのグループ数」より大きかったらグループ数に友達数を設定
ans = max(len(g), ans)

print('答え =>', ans)

[実行結果(入力1の場合)]

友達グループ [0, 1, 4]

友達グループ [2, 3]

答え => 3

1つ目の友達グループが3人ともっとも人数が多いので、3グループに分ければよいことになります。

例えば{0, 2}{1, 3}{4}と分ければ、だれも友達がいないグループとなります。

[実行結果(入力2の場合)]

友達グループ [0, 1, 2, 3]

答え => 4

4人全員が友達なので、4グループに分けて全員をばらばらにする必要があります。

[実行結果(入力3の場合)]

友達グループ [0, 2, 3]

友達グループ [1, 5]

友達グループ [4, 8]

友達グループ [6]

友達グループ [7]

友達グループ [9]

答え 3

1つめの友達グループが3人ともっとも人数が多いので、3グループに分けます。

友達が2人のグループは、3グループのうちいずれかの2グループに振り分ければよいですし、友達がいない人は、3グループのどこに分けても友達関係はできません。

Union Find木

Union Find木

Union Find木 は、グループ分けを管理 することができるデータ構造です。

次のようなことを効率的に行うことができます。

  • 要素aと要素bが 同じグループ に属しているかどうかをチェックする。
  • 要素aと要素bの グループを一つ にまとめる。

(グループ同士をまとめることはできますが、要素をグループから除いたり、グループを分けたりすることはできません)

Union Find木 を実現するためのクラスは以下のようになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
from collections import defaultdict

# n個の要素を0 ~ n - 1のインデックスで管理する
class UnionFind():
def __init__(self, n):
self.n = n # 要素の数
self.parents = [-1] * n # 各要素の親要素の番号を格納するリスト

def find(self, x): # 要素[x]が属するグループの親を返す
if self.parents[x] < 0:
return x
else:
self.parents[x] = self.find(self.parents[x])
return self.parents[x]

def union(self, x, y): # 要素[x]が属するグループと要素yが属するグループとを併合
x = self.find(x)
y = self.find(y)
if x == y:
return
if self.parents[x] > self.parents[y]:
x, y = y, x
self.parents[x] += self.parents[y]
self.parents[y] = x

def size(self, x): # 要素[x]が属するグループのサイズ(要素数)を返す
return -self.parents[self.find(x)]

def same(self, x, y): # 要素[x],要素[y]が同じグループに属するかどうかを返す
return self.find(x) == self.find(y)

def members(self, x): # 要素[x]が属するグループに属する要素をリストで返す
root = self.find(x)
return [i for i in range(self.n) if self.find(i) == root]

def roots(self): # すべての親の要素をリストで返す
return [i for i, x in enumerate(self.parents) if x < 0]

def group_count(self): # グループの数を返す
return len(self.roots())

def all_group_members(self): # 全グループの全要素を返す
group_members = defaultdict(list)
for member in range(self.n):
group_members[self.find(member)].append(member)
return group_members

def __str__(self): # printでの表示用。ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す
return '\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items())

動作確認

実装した Union Find木 の動作を確認してみます。

要素数5個(0,1,2,3,4)のUnion Find木を定義し、[0,1] のグループと [2,3,4] のグループに分けます。

[Google Colaboratory]

1
2
3
4
5
6
uf = UnionFind(5)
uf.union(0, 1)
uf.union(2, 3)
uf.union(3, 4)

print(uf)

[実行結果]

0: [0, 1]

2: [2, 3, 4]

2つのグループに分けることができました。

親の要素(一番もとになる要素) がグループの キー となっていることが確認できます。

次に、要素1と要素3が所属するグループを調べてみます。

[Google Colaboratory]

1
2
print(uf.find(1))
print(uf.find(3))

[実行結果]

0

2

要素1がグループ0に所属し、要素3がグループ2に所属していることが分かりました。

今度は、要素0,要素2が同じグループに属するかどうかと、要素3,要素4が同じグループに属するかどうかを調べます。

[Google Colaboratory]

1
2
print(uf.same(0, 2))
print(uf.same(3, 4))

[実行結果]

False

True

要素0,要素2は違うグループであり、要素3,要素4は同じグループに属することを確認できました。

最後に、要素3が所属するグループの全要素を表示します。

[Google Colaboratory]

1
print(uf.members(3))

[実行結果]

[2, 3, 4]

要素3が所属するグループの全要素は、2,3,4であることが分かりました。

次回は、Union Find木 を使って問題を解いてみます。

線形計画問題(PuLP)

線形計画問題

線形計画問題 は、ある条件下での 領域の最大・最小 を求める問題です。

数理最適化ライブラリPuLP を使うと、線形計画問題 を解くことができます。

[問題]

ある工場で製品 p と製品 q を製造しています。

製品 p と製品 q を製造するには原料 m と原料 n が必要で、次のような条件となっています。

・製品 p を1kg製造するには原料 m が1kg、原料 n が2kg必要。

・製品 q を1kg製造するには原料 m が3kg、原料 n が1kg必要。

・原料 m の在庫は30kg、原料 n の在庫は40kgあります。

・単位量当たりの利益は、製品 p が1万円、製品 q が2万円です。

この条件で利益を最大にするためには、製品 p と製品 q をそれぞれ何kg製造すればよいでしょうか。

製品 p の製造量を x kg、と製品 q の製造量を y kg とすると以下のように不等号をつかった条件式にまとめることができます。

  x + 3y ≦ 30

  2x + y ≦ 40

  x ≧ 0 、y ≧ 0

連立方程式との違いは、等号(==)不等号(≧、≦) になっている点です。

ソースコード

上記の条件式をもとにソースコードを作成すると下記のようになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import pulp

# 第1引数は任意の名前、第2引数は最大化問題を解く指定
problem = pulp.LpProblem('Test', pulp.LpMaximize)

x = pulp.LpVariable('x') # 製品pを製造する量。変数xをpulp.LpVariable関数で定義。
y = pulp.LpVariable('y') # 製品qを製造する量。変数yをpulp.LpVariable関数で定義。

# 線形計画問題の条件式
problem += 1 * x + 3 * y <= 30
problem += 2 * x + 1 * y <= 40
problem += x >= 0
problem += y >= 0

problem += x + 2 * y # 目的関数。最大化する式。

status = problem.solve() # 数理モデルを解く

print('Status:', pulp.LpStatus[status]) # 結果
# xとyの解と利益の関数値
print('x =', x.value(), 'y =', y.value(), 'obj =', problem.objective.value())

[実行結果]

Status: Optimal

x = 18.0 y = 4.0 obj = 26.0

製品 p の製造量を 18kg、製品 q の製造量を 4kg としたときに 利益を最大 にできることが導きだされました。

obj = 26.0 は最大化しようとした 利益の関数値 です。(15行目)

目的関数が x + 2 * y = 26 となることが確認できます。

数理最適化ライブラリ(PuLP)

数理最適化

数理最適化ライブラリ PuLP を使って、連立一次方程式 を解いてみます。

本来の数理最適化ライブラリの使い方とは少々異なりますが、数理モデルを初めて実装するにはとてもよい題材です。

[問題]

1個120円のリンゴと1個150円のミカンを合わせて、10個買ったら代金の合計が1440円でした。

リンゴとミカンをそれぞれ何個買ったでしょうか。

この問題は、リンゴの個数を x、ミカンの個数を y として連立一次方程式を立てることができます。

  120x + 150y = 1440

  x + y = 10

ソースコード

まずは 数理最適化ライブラリ PuLP をインストールします。

[Google Colaboratory]

1
!pip install pulp

連立一次方程式 をもとにソースコードを作成すると下記のようになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import pulp

# 第1引数は任意の名前、第2引数は最大化問題を解く指定(今回は連立一次方程式を解くのでとくに意味はない)
problem = pulp.LpProblem('Test', pulp.LpMaximize)

x = pulp.LpVariable('x') # リンゴの数。変数xをpulp.LpVariable関数で定義。
y = pulp.LpVariable('y') # ミカンの数。変数yをpulp.LpVariable関数で定義。

problem += 120 * x + 150 * y == 1440 # 連立一次方程式を定義
problem += x + y == 10 # 連立一次方程式を定義

status = problem.solve() # 数理モデルを解く

print('Status:', pulp.LpStatus[status]) # 解析結果
print('x =', x.value(), 'y =', y.value()) # xとyの解

[実行結果]

Status: Optimal

x = 2.0 y = 8.0

Optimal は、最適化計算をした結果 最適解 が得られたという意味です。

リンゴの個数は2、ミカンの個数は8となり、合わせて10個 であり、代金の合計も 1440円 で、連立一次方程式の解 として正しいことが確認できます。

部分和問題

部分和問題

深さ優先探索では、一番はじめの状態から遷移を繰り返すことで 全ての状態 を探索します。

したがって、すべての状態に対して操作 を実施したり、全状態を列挙 することが可能です。

[問題]

整数が n個 与えられます。

その中からいくつか選び、その和をちょうど k にすることができるか判定してください。

[条件]

・整数の個数 n は、1以上 20以下

・各整数の値は、-100000000以上 100000000以下

・目標とする数値(部分和) k は、-100000000以上 100000000以下

[解き方]
各整数を1つ目から順番に 加えるかどうか 決めていき、n個すべてについて決め終わったら、その和が k に等しいかどうかを判定します。

再帰関数 を使用します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# ------------ 入力例1 ----------
lst = [1, 2, 4, 7] # 各要素
k = 13 # 目標とする数値(部分和)
# ------------ 入力例2 ----------
# lst = [1, 2, 4, 7] # 各要素
# k = 15 # 目標とする数値(部分和)
# --------------------------------
def dfs(i, total):
print(i,total)
if i == len(lst): # 全部決め終わった場合
return total == k # 今までの和が[目標とする数値]と等しいかどうかを返す

if dfs(i + 1, total): # lst[i]を使わない場合
return True

if dfs(i + 1, total + lst[i]): # lst[i]を使う場合
return True

# lst[i]を使うか使わないかにかかわらず[目標とする数値]がつくれないので False を返す
return False

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

[実行結果(入力例1)]

Yes

2 + 4 + 7 を足し合わせると 13 になるので Yes が解となります。

[実行結果(入力例2)]

No

どんな組み合わせを行っても 15 となることはないので No が解となります。