programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Homework: Solving Knapsack Problem via Bitmaps

Joseph Ibrahim
Greenhorn
Posts: 13
Hello,

So, I'll start this off by admitting that I messed up. I completely forgot about this assignment until last night, and then stubbornly stared at it for hours before trying to seek help. I did manage to find a little bit of help via StackOverflow, but I'm still at a loss, and I stumbled upon this community, so I was hoping you guys could help.

Here's the assignment: Assignment
Basically, we read a file with a bunch of integers. The first line of the file goes into an Array, the second line is the total we're looking for. Using bitOps (and limited to only the starting array), we must generate every possible subset of the array that can add up to the total on the second line.

Frankly, I'm at a complete loss. I can't figure out what to do, or how to proceed forward. Now, I managed to find this: StackOverflow and its the same problem (I'm assuming from a former student, since they mention him by name in comments) and I still can't wrap my head around what I'm supposed to be doing.

Now, I know many of you don't want to give away the answer, and I agree. It's due within a few hours, so I don't mind missing it (I've done every assignment well up until this point), I just really want someone to help me break down step by step, explain what we're doing; so, even if I can't turn it in, at least I know for the future.

Thank you,
Joseph

Jayesh A Lalwani
Rancher
Posts: 2762
32

Basically, the problem here is that this problem is a variation on the "find all possible combinations of this given set" problem. If you don't know what this problem is:- Given a set of numbers, find all the possible combinations of the numbers in the set. If you know how to do solve the find-all-combinations problem, you should be able to solve the given problem. You just have to keep the combinations that add up to the given sum, and throw all the other combinations away

So, the real question is.. how do you find all the combinations?

You could brute force it, and you wouldn;t need the bit ops. Just write a function to find all the combinations, and then go check all the combinations to find the ones you want, and bingo. If I were you and my brain were fried, I would just do this

He has actually given you a solution that he wants here

To generate all possible bit patterns inside an int and thus all possible subsets defined by that bit map would simply require you to start your int at 1 and keep incrementing it to the highest possible unsigned value an unsigned short int can hold (all 1s). At the end of each inner loop, compare the sum to the target. If it matches, you got a solution, if not, try the next subset.

I don't see how his solution is better than brute force

Basically, what he wants you to do is this.. he wants you to make a bit pattern represent which numbers to add up. So, let's say you had only 2 numbers, you will have only 2 bits. So, the possible possible bit patterns are

Here the first bot represents the first number, second the second number. The bot pattern represents which numbers to sum. So,

If any of these combinations leads to a sum, print the combinations

So, the question is how do you generate all combinations of bot patterns. It's pretty easy. First you can find the highest value of the bit pattern, and then you just use a counter. So, if you have 2 numbers, you will have 2 bits, and the highest value of a number with 2 bits is 3(binary 11). If you have 3 numbers, means 3 bits, means the highest value is 7(binary 111). Once you have the highest bot pattern, you just have a simple loop like this

That's it. You have all your combinations of bit patterns.

Now inside this loop, he wants another loop that will go over each bit in the bit pattern, and sum up the number for which the bit is turned 1. If the total comes to the required sum, print out the numbers summed up

Now that I think about it.. I think this solution is neat simply because it doesn't need recursion

Joseph Ibrahim
Greenhorn
Posts: 13
I guess my problem is... how exactly do I do it.
I have up to where you've said so far, here's my code:

My Question is... what do I do next from here? What will the inner for loop look like? I know its asking a lot, but if you could help... even if you could give me some pseudo code or even break down the bitwise operators and help me flesh out their understanding a bit better in my head, it'd be much appreciated.

Thanks,
Joe

Joseph Ibrahim
Greenhorn
Posts: 13
I think I solved it (with some help from my brother).

Is this correct:

Normally, I upload it to his website which checks to see if its correct for you, but its not loading atm. Anyways, this should be right, and to hold the answers I made a String, so printing would be easier.

What do you think?

Thanks,
Joe

Jayesh A Lalwani
Rancher
Posts: 2762
32
BTW, Your loops should start at 1 not 0 .. and you are almost there

Let's take in step by step.. i is your Bitmap. It tells you which numbers to sum up.
i=1.. the bit pattern in 000000000000001. this means you should sum only the first number and nothing else
i=2.. the bit pattern in 000000000000010. this means you should sum only the second number and nothing else
i=3.. the bit pattern in 000000000000011. this means you should sum only the first and second number
.
i=21.. the bit pattern in 000000000010101. this means you should sum only the first and third and fifth number
.
when i=65535, the bit pattern is 1111111111111111, this means you add all numbers

So, let's take i=21.. the bit pattern is 000000000010101.
Now 000000000010101 & 000000000000001 = 000000000000001 .. do add first number
Now 000000000010101 & 000000000000010 = 000000000000000 .. don't add second number
Now 000000000010101 & 000000000000100 = 000000000000100 .. do add third number
Now 000000000010101 & 000000000001000 = 000000000000000 .. don't add fourth number
Now 000000000010101 & 000000000010000 = 000000000010000 .. do add fifth number

Basically, for n =0 to numbers.length-1 if (i & 1 << n) > 0, add nth number to sum

Jayesh A Lalwani
Rancher
Posts: 2762
32
Ok I think your brother's solution will work too.. except that you guys treat 0 as I was treating 1, and 1 as 0. SO, if the bit is 0, you add the number. I am adding the number if the bit is 1. It doesn't matter except that "1 means yes" makes more sense in my head

Joseph Ibrahim
Greenhorn
Posts: 13
Alright,

I changed the loop to start at 1 (not 0, sorry), and the if ((i >> j) % 2 == 0) to if ((i >> j) % 2 == 1).

Is there anything else I'm missing?

Joe

Jayesh A Lalwani
Rancher
Posts: 2762
32
Nah I think your algorithm is correct. as long as you have tested it, you should be good to go