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 weight percent and 63 kg/m^3 respectively near ambient conditions. We also propose ``thermodynamically usable hydrogen capacity" as a criterion for comparing different storage materials.