Question (2) is a known problem; it's called the change-making problem. The Wikipedia page lists integer programming and dynamic programming as solution approaches. The change-making problem is also a variation of the famous knapsack problem. One of the implications of that is that since the standard version of the knapsack problem is NP-complete, it's likely that the change-making problem is as well, dashing hopes for an easy-to-find fast algorithm for solving it.
However, the Wikipedia page also says that for the US and most other coin systems, the greedy algorithm will give the optimal solution. Thus for the nickel/dime/quarter example you give, the optimal solution is to use as many quarters as you can, then account for what's left by using as many dimes as you can, then make up the rest with nickels. So 3 is the minimum number of nickels, dimes, and quarters required to make 40 cents.
Here's the integer program formulation for Question (2). If you let $x_i$ be the number of coins of type $i$ to be used, $d_i$ be the denomination of coin type $i$, and $A$ be the target amount, Question (2) entails solving
$$\min \sum_i x_i $$
subject to
$$\sum_i d_i x_i = A,$$
$$x_i \geq 0, x_i \in \mathbb{Z}.$$
While integer programs are hard to solve in general, for small problems like the example you give a good IP solver will return a solution very quickly. For instance, if you take coins of denominations 31, 37, and 41 cents (since nickels, dimes, and quarters are too easy :) ), and want to know the minimum number required to be equivalent to 2011 cents, the solver Lingo requires only the following code to find the answer:
MIN = x1 + x2 + x3;
31*x1 + 37*x2 + 41*x3 = 2011;
@GIN(x1); @GIN(x2); @GIN(x3);
Lingo outputs the optimal solution as $x_1 = 0, x_2 = 20, x_3 = 31,$ with only 7 solver iterations and "00:00:00" time elapsed. So the minimum number of coins is $51$.
You did ask specifically for an algorithm. Many IP solvers (including Lingo) use the branch and bound algorithm, which has solving a linear program (usually with the simplex method) embedded in it.
For Question (1), you could use the following integer program to find a single solution or determine that one does not exist. (In the latter case, the IP solver will report that the problem is infeasible.)
$$\max 1$$
subject to
$$\sum_i d_i x_i = A,$$
$$\sum_i x_i = n,$$
$$x_i \geq 0, x_i \in \mathbb{Z}.$$
Again, for small problems a good IP solver will return a solution almost instantaneously. I'm not sure how (or even if it's possible) to modify an IP approach to find all solutions like you request. The generating function techniques mentioned by cardinal and in the question linked to by Derek Jennings will tell you how many solutions there are, but I'm not sure if they will tell you exactly what those solutions are.
You need to show the whole problem-we don't have access to Example 7. What is the criterion for "optimum"? Is it the most talks scheduled without overlap, the highest utilization of the hall, or what? You are probably expected to show a list of talks, show what the greedy algorithm produces, and show a better solution (according to the criterion for optimum). Do the talks come with times they have to be given, or are you setting that. This can come from the order you consider the talks-you might scatter a few at various times of the day, preventing many others from being scheduled. If the talks cannot be moved in time, you might schedule a whole batch from the hour to hour plus 5 minutes (only 5 min long), while you have a bunch of hour talks that don't fit any more. If you had scheduled the hours first, you would use the hall all day.
Best Answer
The greedy algorithm isn't always optimal, but it depends on the size of the coins used. For example, consider using coins of size 10, 9, and 1. If you use the greedly algorithm to measure 18, you use 8 1s and 1 10, instead of an optimal 2 9s.
On the other hand, if each coin value is an integer multiple if the next smallest coin value, the greedy algorithm will be optimal. This is not quite the situation we are in, because dimes and quarters differ by a factor of 2.5, but my intuition says this will still not be enough to mess up the optimality of the greedy algorithm.
However, if you get rid of nickels, this changes, because 30 cents is 3 dimes but a quarter and five pennies. Without nickels, no optimal solution to a coin problem will use more than four dimes (why?), But with nickels, an optimal solution won't use more than two dimes. Is this fact enough to show the greedy algorithm is optimal with usual coin amounts?