knapsack related issues

[Mathemalsky]

I thought and read a bit about the knapsack problem.

• performance: In my opinion we should go for the performance improved version of the exact algorithm because it avoids a big amount of memory copies. See here: https://www.cplusplus.com/reference/vector/vector/ The argument that the exact knapsack will perform bad anyway should be discarded due to the fact that the FPTAS version will invoke the exact knapsack problem on the rounded data.
• rounding: The book assumes sizes, values and capacity to be integers. Since our algorithm operates on floats some difficulties concerning rounding occur. The approximation algorithm draws it's polynomial runtime from the fact that the subsets can only take on a finite number of values, namely multiplicities of \mu. Using floats we lose that property. We could treat float as equal if they are within an epsilon environment of each other, but this way comparison loses transitivity which destroys any guarantees in the approximation factor. Do you have any ideas how to deal with that?

[MilchRatchet]

• Ok, then I guess we should look into improving performance there. I suggest we start by making a very large test example and measure time on that one.
• If I am not mistaken this multiplicities of \mu is not an issue regarding float exact comparison. But I will have to think about that again, especially regarding what we do with the values. We can do the epsilon approach where epsilon is at most half of \mu. Alternatively we could implement knapsack for ints. Since C++ has templates we could have one templated implementation which is exposed through a float and int helper function, i.e.

  [...] AAL_KNAPSACK_EXACT([something with ints]);
  [...] AAL_KNAPSACK_EXACTF([something with floats]);
  static [...] AAL_KNAPSACK_EXACT_([something with templates]);

[Mathemalsky]

You can now have a look at the performance comparison. As suspected the pointer version is considerably faster than the initial version. In my test it took about 1.3 s in contrast to the older version, which consumed > 6 s. So if you agree to that point than merge the performance improved version into master. Do we need the performance test any more and should also merge into master?

[MilchRatchet]

Ok, the performance difference is indeed quite massive.

I merged the improved version now. I don't think we should merge the performance test right now. Maybe we could later do a performance test which compares every algorithm for a given problem.