Is there a known solution for the 0/1 knapsack problem that allows the weights of the objects to be real numbers? The only algorithm I can think of is a brute force search. I have tried searching for a solution but couldn't come across any. When weights are natural numbers, the most common solution uses dynamic programming by caching solutions $V[i,w]$ to the subproblems in an $N\times W$ table, where $N$ and $W$ are the number of objects and weight limit of the knapsack. When the weights are real numbers, the dynamic programming solution breaks down: how do you define the table now? Granted there will be $N$ rows, but what about the columns?
3
-
1$\begingroup$ Have you heard of integer linear programming? Have you heard of usage of dynamic programming on knapsack problems? Are the real numbers just floating numbers? Please also indicate your motivation such as the source of the original problem. $\endgroup$– John L.Commented May 22, 2019 at 22:25
-
$\begingroup$ @Apass.Jack Thanks for the comment. I've heard of all of those, and I will edit my solution to elaborate on that. The motivation is pure interest, especially because I did not come across a solution. $\endgroup$– ToniAzCommented May 23, 2019 at 14:22
-
3$\begingroup$ Possible duplicate of What's the time complexity bound for the Knapsack with real weights? $\endgroup$– xskxzrCommented Jul 23, 2019 at 14:16
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
Sort the items by density such that $p_1/w_1\geq p_2/w_2\geq\cdots\geq p_n/w_n$ for profits $p$ and weights $w$. Let $W(k)=\sum_{1\leq i\leq k} w_i$ be the total weight of the first $k$ items in this order. Then for capacity $c$ an optimal fractional solution is to choose items $1,\ldots,i^*$ where $i^*$ is the largest number s.t. $W(i^*)\leq c$ , and additionally a fraction of $(c-W(i^*))/w_{i+1}$ of item $i^*+1$.
Update: I misread your question. For solving the $0$/$1$ version with real-valued weights you can either round them, or apply branch-and-bound algorithms that were designed for real values, e.g. Martello and Toth's MT1R.
$\begingroup$
$\endgroup$
If the weights have a fixed finite precision, you could multiply them by a big number, to turn them into integers.
If the weights have arbitrary precision, it's NP-hard, also known as subset sum problem. There isn't an algorithm taking polynomial time unless P=NP.
Practically, the weights may have a finite, but very high precision, making dynamic programming infeasible. You may have better chance by optimizing a search algorithm, possibly using dynamic programming as a heuristic.
This assumes the values have the same type as the weights. If values are integers or have smaller precision, you could swap values and weights in the algorithm and find the minimum weights by each value.
$\begingroup$
$\endgroup$
1
Well, if it is 0/1 Knapsack problem (i.e. an item is included or not), than it seems trivial to solve it for real-valued weights, provided you have a solution to integer-valued weights variant.
GeeksforGeeks gives a solution for integer weights. You really only need to replace int to double wherever appropriate.
-
4$\begingroup$ How so? The solution of the 0/1 Knapsack problem, also as given in that link you posted, uses a 2-dimensional table of dimensions $N\times W$, where $W$ is the knapsack weight limit. How can you define such a table when the weights are real-valued? You cannot define a continuum of columns in that table. $\endgroup$– ToniAzCommented May 23, 2019 at 14:20