
Title:
1701 Polynomial Time Approximation Scheme

Description:

For some problems, there's no constant factor approximation algorithm unless P=NP

or there are constant factor approximation algorithms

but we know certain limits for how good that constant factor can get.

There are other problems that allow for what is called a PolynomialTime Approximation Scheme

and the idea behind the polynomialtime approximation scheme is basically

that if you put in more running time in to your algorithm,

and that algorithm is called a polynomialtime approximation scheme,

then you will get a better solution or a better guarantee for your solution,

and depending on how good you want that guarantee to be,

then again certain implications for the running time you have to put in.

So, for an almost perfect solution,

you will likely have to put in time that is pretty close to exponential time or even exponential time

and for a solution that iswell, maybe only within a rather course bound of an optimal solution,

you will need less time.

Now, the NP complete problems that we have encountered so far

obviously fall either into the category of having a constant factor approximation algorithm

or admitting no such algorithm

and that is why I'm going to introduce a new NP complete problem to you now called knapsack.

A knapsack is a very simple to describe.

Knapsack gives you as input a set of objects such as these here

and each object has a size and a value and those are both integer number,

so you have an integer size and an integer value and we're soon going to do an example for this,

and then, additionally, you have given a container and that container has a limited capacity,

and that capacity again is an integer,

and the question you're trying to answer with knapsack is actually very simple,

you're trying to ask the question,

"What is the maximum value that I can put into this bag here while observing the limited capacity?"

So the total sum of the size of the objects that I select to be in the knapsack,

so say I select this object to be in the knapsack and this one here

but I don't want this one here,

then that means that the total size of these two objects cannot exceed the capacity of the container

and among all other possibilities of putting objects

into the container without exceeding maximum capacity,

this gives me the best possible value,

and of course, here for the values, we again do the sum to calculate the total value.

Knapsack is known to be NP complete

and now let's do a little example for this problem just to familiarize yourself with this

and I'm going to give you a number of objects here, and of course,

each of these objects has a size and a value.

Now, my question to you is if I give you a container and that container has size 10,

which objects out of these seven here should you put in to the container

to maximize the value without exceeding the size here.

Please check all the items that you should put in to the container to maximize the value.