部分和問題
n 個の整数 a1, a2, …, an, とし、それらのいくつかの和(部分和という)を C とする。
この C になるには、 どの整数が足されていたかを求める問題。
すなわち、 C = a1 m1 + a2 m2 + ... + an mn のとき、 n ビットの (m1, m2, …, mn) を求める問題。
n が大きいと 最新のコンピュータでも 部分和問題を解くことはできません。
n 個の整数 a1, a2, …, an, とし、それらのいくつかの和(部分和という)を C とする。
この C になるには、 どの整数が足されていたかを求める問題。
すなわち、 C = a1 m1 + a2 m2 + ... + an mn のとき、 n ビットの (m1, m2, …, mn) を求める問題。
n が大きいと 最新のコンピュータでも 部分和問題を解くことはできません。