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