We have 135 boxes each containing 100 marbles which look identical and weigh 10 grams, with the exception of one box, which contains hollow marbles of 9 grams each. By using a scale that can weight up to 999 grams, what is the least number of weightings required to determine the box with the hollow marbles?

Step 1
You can do better than $68+67$ on the first weighing! Try $57+56+22$. Take one marble from each of the 56, and two marbles from each of the 22. Then, the scales show either "Error", or "999" or "998". If it shows "error", all 100 marbles on the scales are real, and the hollow marbles are among the 57. If it shows "999", the hollow marbles are among the 56, and if it shows "998", the hollow marbles are among the 22. I will assume worst case in the rest of the explanation, so let's say there are 57 boxes left to examine.
(If the scales say "999" rather than "error" if there are more than 999 grams worth of marbles on it, you will have to do $57+57+21$ instead. This doesn't affect the rest of the algorithm.)
The 57 can be divided further into five groups of $14+14+14+14+1$. Take one marble from each box in one of the 14-groups, two from each the second 14-group, three from each in the third 14-group, and four from the lone box (leaving the fourth 14-group untouched in this round). See whether the scales really show 844, and if not, how many grams are missing.
Step 2
Worst case, you have 14 boxes left after the second weighing. You can now take one marble from box 1, two from box 2, and so on, leaving one box unused. If all marbles on the scales are whole, the scales will show 910, and the unused box will have hollow marbles. If not, count how many grams are missing, and that will identify the box with the hollow marbles.
This totals three weighings. I do not know that this is the best you can do, but I'll be very impressed if anyone comes up with a way to do it in 2.

Step 1
If you place at most 100 marbles on the scale, then you will be able to see exactly how many of them weigh 9 grams. I will assume this is the only viable option. Indeed you can place more than 100 marbles on the scale and get information out of this, but I am very confident that this is never part of an optimal strategy.
Then we can generalize the problem. Assume we have n boxes with m marbles. All marbles from all boxes are identical, except one box has special marbles. We have a machine that we can give an arbitrary collection of m marbles, and it will tell us how many are special. The following describes the optimal strategy for this game.
For x a positive integer, let [x] denote the set {0,...,x}.
Any move can be described by a function $f:[m]\to [n]$ such that f(k) describes the number of boxes from which we take k marbles. Then we need $\underset{k}{\sum <!--\; \sum \; -->}f(k)=n$ and $\underset{k}{\sum <!--\; \sum \; -->}kf(k)\le <!--\; \le \; -->m$. If the machine tells us there are k special marbles, then there are f(k) possible boxes left to check. This means that the worst case is that there are $\underset{k}{max}f(k)$ possible boxes left to check.
Thus, the goal in each step is to minimize $\underset{k}{max}f(k)$ over all functions $f:[m]\to <!--\; \to \; -->[n]$ with $\underset{k}{\sum <!--\; \sum \; -->}f(k)=n$ and $\underset{k}{\sum <!--\; \sum \; -->}kf(k)\le <!--\; \le \; -->m$. We can do this by means of binary search, by checking for specific values of M whether or not it is possible to have $\underset{k}{max}f(k)\le <!--\; \le \; -->M$.
To check whether $\underset{k}{max}f(k)\le <!--\; \le \; -->M$ is possible, let $n=aM+b$ with $0\le <!--\; \le \; -->b<M$. Then assign $f(k)=M$ for $k<a$, $f(a)=b$ and $f(k)=0$ for $k>a$. This gives $\underset{k}{max}f(k)\le <!--\; \le \; -->M$ and $\underset{k}{\sum <!--\; \sum \; -->}f(k)=n$ while minimizing $\underset{k}{\sum <!--\; \sum \; -->}kf(k)$. Thus, we can simply check whether we get $\underset{k}{\sum <!--\; \sum \; -->}kf(k)\le <!--\; \le \; -->m$.
Step 2
Now we can apply this to the case $n=135$, $m=100$. For $M=57$ we find $f=[57,57,21]$ suffices, and for $M=56$ we find $f=[56,56,23]$ does not suffice. Therefore, the optimal strategy is to place 1 marble from 57 boxes and 2 marbles from 21 other boxes. As a result, the worst case scenario is that there are 57 boxes left to check.<br<Then for $M=13$ we find $f=[13,13,13,13,5]$ suffices, and for $M=12$ we find $f=[12,12,12,12,9]$ does not suffice. Therefore, the optimal strategy is to place 1 marble from 12 boxes, 2 marbles from 12 other boxes, 3 marbles from 12 other boxes, and 4 marbles from 5 other boxes. As a result, the worst case scenario is that there are 12 boxes left to check.
Then for $M=1$ we find $f=[1,1,1,1,1,1,1,1,1,1,1,1]$ suffices, and thus we can place 0 marbles from the first box, 1 marble from the secend, etc. up to 11 marbles from the twelveth box. As a result, we will know exactly which box contains the special marbles.
This proves the optimal worst case number of weighings is three. This way, we can also find that the largest number of boxes with which it is possible in three weighings is 140.