# Test (CPU): Knapsack
Implement a parallel solution for the following knapsack problem variation: The input consists of a list of items, each with a size and a priority. For better visualization, imagine a list of movies (e.g., mkv files) that you wish to copy to a portable storage device to take with you on an offline trip (size is the file size in bytes, priority is how much you want to watch the movie). The application is given a range `[min_size, max_size]` of the storage device capacity, and the item selection must fit this range (i.e., the sum of sizes must be greater than or equal to `min_size` and less than or equal to `max_size`). The selected files must have the highest possible total priority (i.e., the sum of priorities of the selected items). If there are multiple selections with the highest total priority, you should return them all. You may use Intel TBB, OpenMP, or any C++ STL features to implement the parallel version of the application.

Imagine the following items as input (listed as size, priority values); the selection range is `[10, 12]`:
```
(5, 3), (5, 5), (6, 4), (7, 2), (2, 2), (3, 3)
```
The following size combinations fit the range (the total priority is in parentheses):
```
5, 5     (8)
5, 6     (9)
5, 7     (7)
2, 3, 5  (10)
2, 3, 6  (9)
2, 3, 7  (7)
2, 5, 5  (10)
3, 7     (5)
```
Note that there are two items of size 5; we use the one with the higher priority (5) in the combinations where only one of them is used. The best total priority is 10; thus, the result will comprise only the combinations `2, 3, 5` and `2, 5, 5`.

Implementation details
The framework, serial implementation, and the testing data are available on `parlab.ms.mff.cuni.cz` (SSH runs on port 42222) in the `/home/_teaching/para/labtest` directory. The serial implementation is in `serial.hpp` (the `operator()` of the `SerialImplementation` class). The parallel version should be implemented in `parallel.hpp`, and the `parallel.hpp` file **is the only file you should submit to ReCodEx**.

The `operator()` returns the best total priority and fills all the corresponding selections into the `results` vector. Each selection is represented as a 64-bit unsigned integer, where the i-th bit (0 is the least significant one) holds the information whether the i-th item is selected (`1`) or not (`0`). Due to this encoding, the maximal number of items is limited to 63.

The main C++ file (`cpu-knapsack.cpp`) performs time measurement of the `operator()` and writes the time in microseconds (us) to the standard output. The output data are stored in a text file (the first line holds the best priority found, and the remaining lines are the selections printed in binary format). The selections are sorted by the framework automatically; you may return them in any order.

## Evaluation
The datasets for the evaluation are available in `/home/_teaching/para/labtest/data`. The number in the name represents the number of items. The `items-*` datasets will be used for performance evaluation, while the `debug-*` datasets can be used for debugging, and they will be tested in ReCodEx to verify correctness. Your implementation may assume that there are at least 10 items (you do not have to optimize for smaller sets). The size range will be left at the default values of the corresponding CLI arguments (i.e., `[9 900 000, 10 000 000]`).

As usual, the harmonic mean of the individual speedups (of the given datasets) will be used to determine your points. The grading table is as follows:

- 3× or less: **0 points**
- 3× to 6×: **1 point**
- 6× to 10×: **2 points**
- 10× to 15×: **3 points**
- 15× or more: **4 points**
The solutions will be tested using 32 and 64 threads on a single worker, and the better of the two results will be graded.

## Hints
To get you started, let us give you a few pointers:

If you aim solely at a recursive solution, it might be wise to limit the depth at which parallelism is used. Usually, you need a few times more parallel tasks than the number of threads (CPU cores) to exploit parallelism, improve load balancing, and keep the overhead of task management low.

Another option is to kick-start the recursion with a parallel for-loop. Take advantage of the fact that the item selection is encoded in a 64-bit unsigned integer, so you can iterate over the entire search space. However, the recursive serial version uses early termination conditions (if the selection exceeds the maximal size), so a purely iterative approach may be less efficient. A combination of iteration (over a selection prefix) with recursion (to complete the selection) may be a good option for parallel implementation.

In your parallel implementation, access to the best-results structure (the best total priority and the corresponding selections) must be synchronized. Using locking mechanisms is possible, but not very efficient. You will definitely need to use some form of privatization, either using a parallel reduction pattern or thread-local storage constructs.