Here, we consider a version of problems with durations and deadlines, which is difficult to solve directly using the techniques we have seen so far.

The Problem. We have a single machine that can process jobs, and a set of requests. We are only able to use this resource for the period between time 0 and time W, for some number W. Each request corresponds to a job that requires time wi to process. Which jobs should we choose if we want to keep the machine as busy as possible before the cut-off time W. Knapsack problem is a more general form of the problem we are trying to solve, where each request i has both a value vi and a weight wi. The goal is to select a subset of maximum total value, as long as the subset's weight does not exceed W. The knapsack problem involves filling the knapsack as much as possible. There is no efficient greedy algorithm that could solve this yet, thus we shall use dynamic programming to solve this problem. We have to come up with a small number of sub problems so that each sub problem can be solved easily form “smaller” ones, and the solution to the original problem, is once the solutions to all the sub problems. The tricky part is figuring out a good set of sub problems.

Designing the Algorithm. Weighted Interval Scheduling is to consider sub problems involving only the first i requests. Our key to solving this problem was to concentrate on an optimal solution O to our problem and consider two cases, depending on whether or not the last request n is accepted or rejected by this optimum solution. For our WIS problem, this was easy because we could simply delete each request that conflicted with request n. In the current problem, accepting request n, does not immediately imply that we have to reject any other requests. Instead, it means that we will accept a subset of requests with an available space less than before. We need more sub problems to get a better solution. To find out the value of OPT(n) we not only need the value of OPT(n-1), but we also need to know the best solution we can get using a subset of the first n-1 items and total allowed weight W-wn. Assume that W is an integer, and all requests have integer weights wi. We will use OPT(i,w) to denote the value of the optimal solution using a subset of items {1,…,i} with maximum allowed weight w. We are looking for the quantity OPT(n,W). If n is not in O, then OPT(n,W)= OPT(n-1,W) or if n is in the solution then OPT(n,W)= wn + OPT(n-1,W-wn). We choose the alternative that gives us the maximum solution. Algorithm is on page 269. Analyzing the algorithm. In our algorithm, we are building up a table of solutions M and we compute each value in it in O(1) time. Thus the running time is proportional to the number of entries in the table. The algorithm runs in O(nW) time. This method is not as efficient as our dynamic program for the Weighted Interval Scheduling Problem, its running time is a function of n and W. We call such algorithms pseudo-polynomial. These kind of algorithms can be efficient when the numbers involved in the input are really small; and they become less practical as these numbers grow large. Given a table M of the optimal values of the sub problems, the optimal set S can be found in O(n) time.

I enjoyed learning how to solve the knapsack problem, and I give this section an 8.5/10.