データ構造,アルゴリズム,デザインパターン総合スレ 4 (105レス)
前次1-
抽出解除 必死チェッカー(本家) (べ) 自ID レス栞 あぼーん

リロード規制です。10分ほどで解除するので、他のブラウザへ避難してください。
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})
58: 2021/10/25(月)16:58 ID:Ex1ycVpJ(2/2)調 AAS
Introduction to Algorithms 3rd Editionがくどすぎて読みにくい。
前次1-
スレ情報 赤レス抽出 画像レス抽出 歴の未読スレ AAサムネイル

ぬこの手 ぬこTOP 0.017s