We perform an extensive combinatorial search for optimal nanostructured hydrogen-storage materials among various metal-decorated polymers using first-principles density-functional calculations. We take into account the zero-point vibration as well as the pressure- and temperature-dependent adsorption-desorption probability of hydrogen molecules. An optimal material we identify is Ti-decorated cis-polyacetylene with reversibly usable gravimetric and volumetric density of 7.6 wt % and 63 kg/m(3), respectively, near ambient conditions. We also propose "thermodynamically usable hydrogen capacity" as a criterion for comparing different storage materials.