This problem has many real world applications and is interesting because no one has ever found an algorithm that guarantees to find the solution without requiring work that is proportional to trying every possible combination (subset) of size 1 or more weights from the bag.
From a set of N elements it is possible to generate 2 to the N subsets (the null set is always a subset of any set). This set containing all subsets is called the power set. If a given set has N elements, then its power set has 2 to the N elements.
There are a few ways to generate those subsets such as writing nested loops (awkward), using recursion (more elegant but still not the simplest), or using bitmaps (very easy).A bit map is an association we make between a bit (1/0 or T/F) and an element of a set. The association is simple. For every element in the set we assign one bit to correspond to one element of the set. The correspondence is defined as a 1 indicating inclusion into the subset, and a 0 meaning exclusion from the subset. If our set has N elements then we need N bits to map onto each set element.
original set: { 12 21 13 31 14 41 15 51 16 61 17 71 18 81 77 34 }
our bitmap: { 1 0 1 1 0 1 1 1 1 0 1 1 0 0 1 0 }
the subset indicated: { 12 13 31 41 15 51 16 17 71 77 }
Notice that only where the associated bit is a 1, do we include that element in our subset. Bits that are 0 cause the exclusion of their associated set element. The remaining questions is: "What tools does Java give us to set up this mapping and generate all the possible subsets?"
We will not actually use the actual bits inside integers as our bits because bit shift operations would then be required to isolate individual bits. Instead we will use a String of '1's and '0's as out bitmap, and each individual '1' or '0' char will serves in place of a bit. It is simple to convert an int to a String of 1s and 0s. A simplified version of our toBitString() function from project #1 will serve the purpose for this project #4.
Watch how this demo program uses a simple loop to generate a sequence of ints - and then converts the number to a bit string. That bit string then serves as the bitmap that is used to select or filter a subset from the original set.
Your task will be to adapt this demo such that it only selects and prints those subsets whose elements sum up to the specified total.Write a Java program that takes 1 command line arg which is the input file name and finds all the subsets of the original set that sum to the specified target number. You program must print a report to stdout that is formatted like this:
27 98 87 76 32 46 35 24 13 <-- this is a subset of the original set. It sums to 438 27 98 87 76 80 57 13 <-- these subset lines do not have to be in any particular order 27 98 87 76 80 46 24 <-- each one must however sum to 438 27 98 87 65 43 46 35 24 13 <-- and the number of subset lines must match my solution's number exactly ... etc. for each subset found that sums to 438
To account for this my grading script will sort the lines of your out such that it can be diffed against a "correct" output file. When you examine your output it may be difficult to visually match against mine. You can count the number of lines in your output and confirm it matches the number of lines in mine. Once you hand it in the script will be the definitive judge.
| input file | correct sorted output |
|---|---|
| input-1.txt | sorted-correct-output #1 |
| input-2.txt | sorted-correct-output #2 |
| input-3.txt | sorted-correct-output #3 |
A correctly written algorithm is capable of generating duplicate subsets. This is a natural consequence of generating every possible subset on sets that have duplicate elements. Do not bother to purge duplicate subsets. If you do, you will not match my output. Just generate all the subsets and print all that match the target sum.