Combinations? (edited 03062004)

[b][red]This message was edited by jarola at 2004-6-2 22:8:8[/red][/b][hr]
[b][red]This message was edited by jarola at 2004-6-2 3:50:45[/red][/b][hr]
[b][red]This message was edited by jarola at 2004-6-2 2:19:38[/red][/b][hr]
Hello all!

First of all i'd like to say that i'm sorry for my bad english! If there is/are some part(s) you don't understand, please reply anyway and ask me to clear that!

Solving a knapsack problem
--------------------------

How can i print all the combinations (not permutations) of N positive integers?
F.ex. integers [1 2 3]
-->
|1 | 1 2 | 1 2 3 | 1 3 | 2 | 2 3 | 3 |

This info is needed in solving 1-0 knapsack problem, so if someone has any ideas about this problem feel free to tell!

Edit:
Does this relate to the above problem somehow?
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

If i store all the item records in a linear list, and each record had a binary field (called "included" or something), could i use the binary combinations from above and how?
Just wondering...
---------------------
Second edit:

Ok, now i've generated a file full of bitmasks (binaries whose decimal values equal 0-N).
Idea is to pull a bitmask from this file and use it to select items into knapsack.
At this stage if number of items is too small, items don't fit into knapsack etc. then that combination is dropped, else it will be saved into a file of records.
This will be repeated 2^AmountOfItems-1.
Finally the file of records will be processed in two phases, on first run the best item combination is looked up.
On second run all the other combinations with the same value will be looked up.

Ok, there is the theory then...there HAS to be an easier way to do this!
I feel like climbing a tree feet first...

- J






Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories