Returns k items without replacement from a weighted sample.
The input is a dictionary of items with weights as values.