データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4 (105ﾚｽ)
上下前次1-新
57: 2021/10/25(月)12:10 ID:Ex1ycVpJ(1/2) AAS
以下のような感じで証明できないですかね？
タスク T のポイントを p(T) で表すことにする。
貪欲法によって選ばれたタスク列を
T_1, T_2, …, T_n
とする。
S := {(S_1, S_2, …, S_k) | 1 ≦ k ≦ n, S_i は第i日に行うタスク, p(S_1 + … + S_k) > p(T_1 + … + T_k)}
S が空集合ではないとして矛盾を導く。
(S_1, S_2, …, S_l) を長さが最小の S の元とする。
p(S_1) + … + p(S_{l-1}) ≦ p(T_1) + … + p(T_{l-1})
上下前次1-新書関写板覧索設栞歴
あと 48 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ
ぬこの手 ぬこTOP 0.003s