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