差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン | 次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:dynamic_programming:subset_convolution [2020/02/12] – [意味合い] ikatakos | programming_algorithm:dynamic_programming:subset_convolution [2020/02/13] – [定義] ikatakos | ||
|---|---|---|---|
| 行 20: | 行 20: | ||
| * それぞれの部分集合につき、何らかのスコアが決まっている | * それぞれの部分集合につき、何らかのスコアが決まっている | ||
| - | * ある部分集合 $S$ について、$S \subseteq T$ となるような全ての $T$ のスコアの総和を求める | + | * ある部分集合 $S$ について、$S \subseteq T$ となるような全ての $T$ のスコアの総和を求めたい |
| 部分集合 | 部分集合 | ||
| 行 26: | 行 26: | ||
| | | ||
| S = {1} → T = {1}, {0, 1}, {1, 2}, {0, 1, 2} | S = {1} → T = {1}, {0, 1}, {1, 2}, {0, 1, 2} | ||
| - | | + | スコアの総和 |
| * これを全ての部分集合について行うのが「ゼータ変換」であり、高速に行うアルゴリズムを「高速ゼータ変換」という。 | * これを全ての部分集合について行うのが「ゼータ変換」であり、高速に行うアルゴリズムを「高速ゼータ変換」という。 | ||
