データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4 (105ﾚｽ)
データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4 http://mevius.5ch.net/test/read.cgi/tech/1580131715/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
必死ﾁｪｯｶｰ(本家)
(べ)
自ID
ﾚｽ栞
あぼーん
59: デフォルトの名無しさん [] 2021/10/26(火) 11:19:31.94 ID:CwYCZWUI タスク T のポイントを p(T) で表すことにする。 貪欲法によって選ばれたタスク列を T_1, T_2, …, T_n とする。 S := {k | 1 ≦ k ≦ n, 第1日目から第k日目の間に得られるポイントの合計の最大値 > p(T_1) + … + p(T_k)} が空集合ではないと仮定して矛盾を導く。 k_0 := min S とおく。 第1日目から第k_0日目の間に得られるポイントの合計の最大値を達成するタスク列を S_1, S_2, …, S_{k_0} とする。 仮定により、 p(S_1) = p(T_1) p(S_2) = p(T_2) … p(S_{k_0-1}) = p(T_{k_0-1}) p(S_{k_0}) > p(T_{k_0}) が成り立つ。 http://mevius.5ch.net/test/read.cgi/tech/1580131715/59
60: デフォルトの名無しさん [] 2021/10/26(火) 11:33:36.58 ID:CwYCZWUI このとき、長さ n のタスク列 S_1, S_2, …, S_{k_0-1}, R_{k_0}, R_{k_0+1}, …, R_{n} で p(R_{k_0}) = p(T_{k_0}) p(R_{k_0+1}) = p(T_{k_0+1}) … p(R_{n}) = p(T_{n}) を満たすようなものが存在することは明らかである。 このタスク列 S_1, S_2, …, S_{k_0-1}, R_{k_0}, R_{k_0+1}, …, R_{n} も貪欲法によって選ばれうるタスク列である。 ところが、タスク列 S_1, S_2, …, S_{k_0-1}, R_{k_0}, R_{k_0+1}, …, R_{n} は第k_0日において、 p(S_{k_0}) > p(T_{k_0}) = p(R_{k_0}) であるにもかかわらず、 タスク S_{k_0} を選択しないタスク列であるから、このタスク列は貪欲法によって選ばれうるタスク列ではない。 これは矛盾である。 よって、 S は空集合である。 http://mevius.5ch.net/test/read.cgi/tech/1580131715/60
ﾒﾓ帳
(0/65535文字)
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.530s*