Suppose there are 1000 prisoners, each one of them can be given a sample of wine from each of the 1000 bottles and within 4 weeks, one must die and we know the poisoned bottle (assuming no one else dies due to other reason :D)
Now, let there be 999 persons. Now, we can have 1 person taste wine from 2 bottles and after 4 weeks, either one person dies or 2 persons die -> in any case we know the poisoned bottle.
Now we can do smarter. (Better solution)
Let the bottles be numbered $1,2,3, \dots , 1000$. Now, we can make two solutions from bottles $1-500$ and $501-1000$ respectively. Give these two to most troublesome prisoners. At least one must die within 4 weeks, but we cannot wait for it. So, simultaneously we proceed as follows:
For $1-500$ solution, we make another solution of $1-250$ and $251-500$ before head and similarly for $501-1000$. So, now we kill maximum 2 person and we find which of the 250 bottles contains the poisoned one.
Going like this, with 3 killing, we find 128 possible poisoned ones,
with 4, 64,
with 5, 32,
with 6, 16,
with 7, 8,
with 8, 4,
with 9, 2,
with 10, 1.
Essentially we are traversing a binary tree and we are sure to kill 10 person when we find the poisoned bottle. (King should ensure good prisoners are at bottom of tree and bad ones at top :D )