Rendered at 10:23:46 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
TacticalCoder 2 hours ago [-]
0/1 Knapsack is a wonderful little problem, especially with its dynamic programming solution.
Now I may be mistaken but when I learned about 0/1 Knapsack three decades ago, my immediate thought was that for quite some cases you could do, using dynamic programming, an approximate version (requiring less memory and hence well, for example fitting into memory) and prove that your solution was "at most 1% off of the optimal solution". Never really looked into it though so I may have be wrong.
Basically say you need to 0/1 Knapsack the quantities 1739, 2989, 3798 and 4233, etc.: you can e.g. divide them by 10 and then round them up, so you've now got 174, 299, 380 and 424 and you need much less memory to run your dynamic programming solution to 0/1 Knapsack. And the best solution you find is guaranteed to be at most x% off the optimal solution.
Something like that. Does that work? Anyone ever heard about something similar?
Now I may be mistaken but when I learned about 0/1 Knapsack three decades ago, my immediate thought was that for quite some cases you could do, using dynamic programming, an approximate version (requiring less memory and hence well, for example fitting into memory) and prove that your solution was "at most 1% off of the optimal solution". Never really looked into it though so I may have be wrong.
Basically say you need to 0/1 Knapsack the quantities 1739, 2989, 3798 and 4233, etc.: you can e.g. divide them by 10 and then round them up, so you've now got 174, 299, 380 and 424 and you need much less memory to run your dynamic programming solution to 0/1 Knapsack. And the best solution you find is guaranteed to be at most x% off the optimal solution.
Something like that. Does that work? Anyone ever heard about something similar?