items$=\{9\mathrm{.}3,24,14,5,8,17,4\mathrm{.}2\}$ k$=20$ EXAMPLE USAGE :

We study a knapsack problem, defined as follows: Given as input a knapsack of size $K$

and $n$

items whose sizes are $k_1,k_2,$dots,$k_n,$ where $K$ and $k_1,k_2,$dots,$k_n$ are all positive real numbers,

the problem is to find a full "packing" of the knapsack $($i$.$e$.,$ choose a subset of the $n$ items

such that the total sum of the sizes of the items in the chosen subset is exactly equal to $K).$

It is well known that the knapsack problem is NP$-$complete, which implies that it is very likely

that efficient algorithms $($i$.$e$.,$ those with polynomial runtime$)$ for this problem do not exist.

Thus, people tend to look for good approximation algorithms for solving this problem. In

this exercise, we relax the constraint of the knapsack problem as follows.

We still seek a packing of the knapsack, but we need not look for a "full" packing of the

knapsack; instead, we look for a packing of the knapsack $($i$.$e$.,$ a subset of the $n$ input items$)$

such that the total sum of the sizes of the items in the chosen subset is at least $\frac{K}{2}($but no

more than $K).$ This is called a factor of $2$ approximate solution for the knapsack problem.

To simplify the problem, we assume that a factor of $2$ approximate solution for the knapsack

problem always exists, i$.$e$,$ there always exists a subset of items whose total size is at least

$\frac{K}{2}$ and at most $K.$

For example, if the sizes of the $n$ items are $\{9,24,14,5,8,17\}$ and $K=20,$ then $\{9,5\}$ is a

factor of $2$ approximate solution. Note that such a solution may not be unique. For example,

$\{9,8\}$ is also a solution. Also note that the item sizes may not be integers $($but are positive

real numbers$),$ although they are integers in this example.

Design a polynomial time algorithm for computing a factor of $2$ approximate solution, and

analyze the running time of your algorithm $($using the big$-.$We study a knapsack problem, defined as follows: Given as input a knapsack of size K and n items whose sizes are ki$,$ k$2,...,$ kn$,$ where K and kj$,$ ka$,...,$ kn are all positive real numbers, the problem is to find a full "packing" of the knapsack $($i$.$e$.,$ choose a subset of the n items such that the total sum of the sizes of the items in the chosen subset is exactly equal to K$).$ It is well known that the knapsack problem is NP$-$complete, which implies that it is very likely that efficient algorithms $($i$.$e$.,$ those with polynomial runtime$)$ for this problem do not exist. Thus, people tend to look for good approximation algorithms for solving this problem. In this exercise, we relax the constraint of the knapsack problem as follows. We still seek a packing of the knapsack, but we need not look for a "full" packing of the knapsack; instead, we look for a packing of the knapsack $($i$.$e$.,$ a subset of the n input items$)$ such that the total sum of the sizes of the items in the chosen subset is at least K$/2($but no more than K$).$ This is called a factor of $2$ approrimate solution for the knapsack problem. To simplify the problem, we assume that a factor of $2$ approximate solution for the knapsack problem always exists, i$.$e$,$ there always exists a subset of items whose total size is at least K$/2$ and at most K$.$ For example, if the sizes of the n items are $\{9,24,14,5,8,17\}$ and K $=20,$ then $\{9,5\}$ is a factor of $2$ approximate solution. Note that such a solution may not be unique. For example, $\{9,8\}$ is also a solution. Also note that the item sizes may not be integers $($but are positive real numbers$),$ although they are integers in this example. Design a polynomial time algorithm for computing a factor of $2$ approximate solution, and analyze the running time of your algorithm $($using the big$-$O notation$).$ Note that although there may be multiple solutions, your algorithm only needs to find one solution. If your algorithm runs in O$($n$)$ time and is correct, then you will get $5$ bonus points. Note: I would like to emphasize the following, which applies to the algorithm design questions in all assignments in this semester. $1.$ Algorithm Description You are required to clearly describe the main idea of your al$-$ gorithm. $2.$ Pseudocode The pseudocode is usually very helpful for explaining the algorithm. So you are strongly encouraged to provide pseudocode for your algorithm. $3.$ Correctness You also need to explain why your algorithm is correct. For instance, for this knapsack problem you need to explain why your algorithm can produce a factor of $2$ approximate solution. $4.$ Time Analysis You are required to analyze the running time of your algorithm.