0/1 Knapsack with irrational weights
- by user356106
Consider the 0/1 knapsack problem.
The standard Dynamic Programming algorithm applies only when the capacity as well as the weights to fill the knapsack with are integers/ rational numbers. What do you do when the capacity/weights are irrational?
The issue is that we can't memoize like we do for integer weights because we may need potentially infinite decimal places for irrational weights - leading to an infinitely large number of columns for the Dynamic Programming Table .
Is there any standard method for solving this? Any comments on the complexity of this problem? Any heuristics?
What about associated recurrences like (for example):
f(x)=1, for x< sqrt(2)
f(x)=f(x-sqrt(2))+sqrt(3)