データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4 (105ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
59: 2021/10/26(火)11:19:31.94 ID:CwYCZWUI(1/2)調 AAS
タスク 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})
が成り立つ。
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.019s