In this lesson, we're going to look at the Knapsack problem. In this and the coming lessons, we're then going to get a polynomial time approximation scheme for this Knapsack problem. So, what is the problem? Well, one way to think about it is that we go on a hiking trip and there are lots of items that we could take with us on our trip, but we don't want to carry too much weight. Let's say that we want to select a subset of the items that we might take, and this subset should not weigh more than let;s say 10 kilograms. So, what you can do is you assign a value to each of the items that you could perhaps take. How useful is it for you on your trip? And then the problem that you want to solve is, given this large collection of items, select a subset of items that weighs at most ten kilograms and whose total value for you on your trip is maximized. So, let's define that more formally and introduce a little bit of notation. So, I have a set x of n items. Each item xi has a weight, weight of xi, which is positive and it has a value which is also positive. Okay. Another part of the input is a parameter w, which tells us how much weight we want to carry. Now, the goal is to select a subset of the items such that the sum of the values is maximized. Okay. So, this is a maximization problem. The constraint is that the sum of the weights of the items that I select is at most w. So, let's look at a simple example. Here you see six items with different values and different weights. Let's say that again, our threshold for the maximum total weight is 10. Well, there are many different feasible solutions, for instance, we could just decide to take this one item which is very valuable. It has value 17.5, but it also weighs quite a lot. So, if we select this item, actually we cannot select anything else. So here if we just select item four, then the total weight is 9.4, so it's within the weight limit, that's fine, and the total value is 17.5. But as you can see, if you look a little bit longer, then there are actually better solutions than this. For instance, if we select items one, three, five, and six, if we do the computations then you see that the total weight of these items is still within the weight limit of 10, and the total value is more than just selecting the single item four of high value. So the problem is we're given these items with weights and values, find an optimal subset which is a subset where the constraint is that its total weight should be at most w, and the sum of the values is maximized. So, what our goal is going to be in the coming lectures is to get a PTAS for this Knapsack problem. Remember that a PTAS is an algorithm that has two parameters. An input instance, in this case that will be the set of weights and values, and a parameter epsilon that specifies how close to the optimal solution we want to get. For maximization what we want is that the solution for this PTAS, that the PTAS computes, is at least one plus epsilon times the optimal solution. So, that's the plan. The way we're going to do that is using a global strategy that you can also use for certain other problems. So the global strategy is the following. So first, we're going to replace the values by different values which are integers. The idea is that for integer values the problem is hopefully going to be easier. Then, we're going to solve the problem for these integer values, and then that solution simply tells us select this and this and this item and then that's the solution we're going to report. So, to make this scheme work, we need two properties. First of all, if we change these values to value*, if we change the values to integer values, then the optimal solution that you get for these new integer values should give us a good approximation of the optimal solution for the real values. Somehow we have to make sure that this is the case. Then, if we can do this, the second ingredient that we need is that once we have integer values, and actually the idea is that we're going to make sure that these integer values are not too large in a certain sense. So, once we have an instance with relatively small integer values, then we should be able to solve it in polynomial time. This is going to be the global strategy, and the next lessons we're going to see how to apply this global strategy in case of the Knapsack problem.