Tests contains contradictory tests.
One says if budget = 0 then return = ""
Other says if budget = 0 then return = "0"

Ruby should be updated to 3.0

You can simplify the Haskell tests:

it "works for random positive integers" $ property $ \(Positive budget) ->
  forAll (listOf1 $ oneOf [choose (4900, 5000), choose (28, 299)]) $ \prices ->            
    search budget prices `shouldBe` searchSol budget prices

Or, to actually test arbitrary positive integers:

it "works for random positive integers" $ property $ \(Positive budget) ->
  forAll (fmap (map getPositive) arbitrary) $ \prices ->            
    search budget prices `shouldBe` searchSol budget prices