I'm doing a 0/1 knapsack algorithm in C.
I'm retrieving the items and yours respective informations from a database to use in algorithm.
Counting this items, I have the total of 18k items.
For this motive I was oriented to make a knapsack using only 2 rows.
But now I don't know how to get the items from this optimization. This happens because I don't have anymore a table to analise the values.
I found this topic: Talk about 3 methods of knapsack implementation. I`m using a variation of method 2.
And I found this other topic: Talk about how to find elements in a normal way of 0/1 knapsack using all values of the table.
So, my Question is: How to find the items of a 0/1 knapsack using a 2 rows implementation, once the table don't have the rest of values? I don't understand how to get this elements without all the table :(
P.S.: Sorry for my English
UPDATE: Possible Solution?
I thought in a simple solution, but it is very simple and costly.
I'm thinking to use 1 byte per 8 item. In other words every bit of this byte can be considered like a bit id.
The ideia behind of this is set this "tracking bytes" for every cell in other 2 rows knapsack table, like a clone of the first table but with "tracking bytes" not profit value.
An example of this:
If I have 5 Itens, soon I have 1 byte.
My bag have the capacity, for exemple, of 10.
Soon my knapsack table will be 11 columns and 6 lines, but with optimization the lines will be count like 2, and my "tracking bytes" knapsack table will be the same columns and lines count.
If we count the space for used for this "tracking table" will be of:
1 byte per cell
11*2 cells = 22 cells
22*1 byte = 22 bytes for all table.
So, this is the way I'm thinking. What you think about this? Feel free to comment
See this 0/1 knapsack problem. I have solved it by using two rows.
In 0/1 knapsack only current row and previous row matters so we can easily do it by 2 rows.
I haven't tried backtracking with two rows but i guess it might be possible.
Dushyant,
I know this is possible. But I don't know how to do this. :(
Do you have any ideia?
So many downvotes. I guess I didn't understand the question correctly.
Here's one solution:
Consider a table with n rows and C columns. This is the dp table for standard 0/1 knapsack. The solution to the knapsack problem is a path through this table from (0, 0) to (n, C). We say the parent of (i, j) is either (i — 1, j) or (i — 1, j — w[i]), depending on which choice gives higher value, and we have enough capacity to take item i.
Now if we know the path taken through the dp table, we can reconstruct the elements in the knapsack (an edge from (i, j) to (i — 1, j — w[i]) means item i was taken). Let's work on finding a path through the table. Actually, let's do one simpler. Let's find a single element on the path from (0, 0) to (n, C).
When you reach row n/2, create a new ancestor array where each element points to itself. Now as you update your two rows, in your ancestor array, keep track of which cell in row n/2 is the parent of each cell in your current row. This can be done without changing the time complexity of 0/1 knapsack.
At the end, you know the ancestor of (n, C) that is in row n/2. Let this spot be (i, j). You know that every ancestor of (i, j) is some spot (i', j') with i' < i and j' <= j. Similarly, every cell on the path from (i, j) has value between (i'', j'') with i < i'' < n and j <= j'' <= C. Splitting the table along (i, j) divides the table into 4 sections, but we are only concerned with two of them. Thus, we can rerun knapsack with these modifications on those two subtables.
Knapsack has runtime of O(nC). Re-running knapsack on the two subtables is O(nC / 2). Those get split into further subtables with total size O(nC / 4). Since 1 + 1/2 + 1/4 + 1/8 + ... = 2, Our algorithm still has time O(nC), and still uses O(C) space (using the same series argument).