A moduli space of sheaves satisfies weak Brill-Noether if the general sheaf in the moduli space has no cohomology. Goettsche and Hirschowitz prove that on the projective plane every moduli space of Gieseker semistable sheaves of rank at least two and Euler characteristic zero satisfies weak Brill-Noether. We completely characterize Chern characters on Hirzebruch surfaces for which weak Brill-Noether holds. We also use combinatorial methods to prove that on a del Pezzo surface of degree at least 4 weak Brill-Noether holds if the first Chern class is nef. This is joint work with Izzet Coskun.