Module knaptime::continuouszeroone

Continuous 0-1 Knapsack

A variant of the knapsack problem.

Normally you need to have fixed precision in order to calculate the optimal solution. Floating point numbers have too much precision. You might be able to get away with using dpwalkback, but not when there’s a lot of items.

An alternative approach is to use probability to find a solution that has some % chance of fitting/being the optimal solution. There’s a percentage chance that it’ll be the optimal solution/undershoot/overshoot, but the distribution should be centered around the optimal solution.

TODO: Do the actual math/experimentally verify this

Given a list of items with associated weights and values, choose at most one of each given item. Maximize the value while ensuring the weight less than or equal to a given capacity.