Iterating X times (where X > Y) over Y element dictionary
You can solve this mathematically. Let's suppose there are \$m\$ hosts and \$n\$ jobs. Sort the hosts into ascending order by their slots, so that \$s_i\$ is the number of slots for host number \$i\$, and we have \$s_0 ≤ s_1 ≤ \dotsb ≤ s_{m−1}\$.

Now we can immediately figure out how many jobs host 0 gets. Case (i): if \$s_0m ≥ n\$, then we can distribute jobs evenly across the hosts, so that every host gets either \$\lceil{n \over m}\rceil\$ or \$\lfloor{n \over m}\rfloor\$ jobs. Because jobs are distributed to the hosts with higher capacity first, we can be sure that host 0 gets \$\lfloor{n \over m}\rfloor\$ jobs. Case (ii): if \$s_0m &lt; n\$, then we have to give each host at least \$s_0\$ jobs (and some hosts more).

So host 0 gets \$\min(\lfloor{n \over m}\rfloor, s_0)\$ jobs, and then we can subtract 1 from \$m\$ and go on to host 1. Like this:

import operator

class CapacityError(Exception):
    pass

def schedule(hosts, n):
    """
    Generate a schedule for picking `n` slots from `hosts` (a
    dictionary mapping hostname to capacity). Raise CapacityError if
    no such schedule is possible.

    &gt;&gt;&gt; sorted(schedule({'A': 3, 'B': 7, 'C': 1}, 8))
    [('A', 3), ('B', 4), ('C', 1)]
    """
    if n &gt; sum(hosts.itervalues()):
        raise CapacityError()
    m = len(hosts)
    for host, slots in sorted(hosts.iteritems(), key=operator.itemgetter(1)):
        j = min(n // m, slots)
        n -= j
        m -= 1
        yield host, j
    assert(n == m == 0)


Update 1: generators

I've implemented this function in the form of a generator because that's the most flexible way in Python to produce a sequence of things (here, elements of a schedule). You can easily turn the result into a dictionary:

&gt;&gt;&gt; dict(schedule({'A': 3, 'B': 7, 'C': 1}, 8))
{'A': 3, 'C': 1, 'B': 4}


or a list:

&gt;&gt;&gt; list(schedule({'A': 3, 'B': 7, 'C': 1}, 8))
[('C', 1), ('A', 3), ('B', 4)]


or just process the items one at a time:

&gt;&gt;&gt; for host, slots in schedule({'A': 3, 'B': 7, 'C': 1}, 8):
...     print("{}: {}".format(host, slots))
... 
C: 1
A: 3
B: 4


(If you're not happy with using generators, you can easily change the implementation to return a dictionary instead. But it's worth learning to use them. See the Python Tutorial, or this question on Stack Overflow.)

Update 2: job ids

You asked in comments how to assign individual jobs. Well, one idea would be to pass in a list of jobs to the scheduler, and get out a list of jobs for each host, like this:

from itertools import islice

def schedule2(hosts, jobs):
    """
    Generate a schedule for assigning the list `jobs` to `hosts` (a
    dictionary mapping hostname to capacity). Raise CapacityError if
    no such schedule is possible.

    &gt;&gt;&gt; jobs = ['j{}'.format(i) for i in range(8)]
    &gt;&gt;&gt; dict(schedule2({'A': 3, 'B': 7, 'C': 1}, jobs))
    {'A': ['j1', 'j2', 'j3'], 'C': ['j0'], 'B': ['j4', 'j5', 'j6', 'j7']}
    """
    n = len(jobs)
    if n &gt; sum(hosts.itervalues()):
        raise CapacityError()
    m = len(hosts)
    jobs = iter(jobs)
    for host, slots in sorted(hosts.iteritems(), key=operator.itemgetter(1)):
        j = min(n // m, slots)
        n -= j
        m -= 1
        yield host, list(islice(jobs, j))
    assert(n == m == 0)


Update 3: more explanation

You asked in comments for more explanation. Well, I'm going to assume that you know all about Python iterables, iterators, and generators (see the Python tutorial and the answers to this question on Stack Overflow).

So the remaining difficult bit is why I write jobs = iter(jobs) and list(islice(jobs, j)). Remember that jobs is a sequence of jobs, and we want to split it up into lists of jobs assigned to each host. In the line

        j = min(n // m, slots)


we compute the number of jobs to assign to the current host, so what we need to do is to take the next j elements from the list jobs. One way to do that would be able to keep a counter k of how far we got through the list jobs, and then take a slice of the next j elements starting at k. Like this:

    k = 0
    for host, slots in sorted(hosts.iteritems(), key=operator.itemgetter(1)):
        j = min(n // m, slots)
        n -= j
        m -= 1
        yield host, jobs[k:k+j]
        k += j


There's nothing wrong with doing it like this, except that it's a bit of a pain keeping the counter k up to date. We don't really care about the value of k, we just want the next j elements from jobs, whatver they are. That's where itertools.islice comes in. The call islice(iterator, j) returns an iterator that takes j elements from iterator. Which is almost exactly what we need, except that it's an iterator, but we need a list. So we convert it to a list by calling the built-in function list.

Here's an example showing islice in action:

&gt;&gt;&gt; from itertools import count, islice
&gt;&gt;&gt; c = count(1) # an iterator that counts upwards from 1
&gt;&gt;&gt; a = islice(c, 5) # an iterator that gets 5 elements from c
&gt;&gt;&gt; list(a)
[1, 2, 3, 4, 5]
&gt;&gt;&gt; list(islice(c, 3)) # get another 3 elements from c
[6, 7, 8]


The only remaining problem with using islice to split up jobs is that this relies upon jobs being an iterator (a list won't work). So we use the built-in function iter to ensure that jobs is an iterator.

You should try out all these functions in the interactive interpreter to get a feel for what they do and how they work.

You also asked about assert. An assertion is a statement that tests a value and raises an exception if it's not true. It declares a condition that must be true at this point in the program. This is useful for programmers who want to read and understand the code, and it also catches implementation errors if these lead to the condition being violated. See Wikipedia on assertions.

In this case, I want to declare that the program has generated an assignment for every host (that is, m == 0 since m starts at the number of hosts and counts down for each one) and that every job has been assigned to some host (that is, n == 0, since n starts at the number of jobs, and gets reduced by j when we assign j jobs to some host).