These are some observations about this exercise that may be useful in solving it, that I got from the usenet group. Francis Glassborow wrote: Yes, the problem requires you to write a program that implements some strategy for balancing the two sets. One such strategy might be to try swapping pairs between sets. But in the case you have just moving some of the small values from one set to the other would get you closer. Part of the purpose of this exercise is to help the student to realise that there is much more to programming than simply writing lines of code. Actually it is all the rest that is hard :-) .... One strategy that will produce a first approximation is to start with two empty totals and then iterate over 1 to 100 adding the square root to which ever total is currently the lowest: value sqrt A B 1 1 1 0 2 1.4142136 1 1.4142136 3 1.7320508 2.7320508 1.4142136 4 2 2.7320508 3.4142136 5 2.2360679 4.9681187 3.4142136 and so on but eventually you will reach a position in which you add successive values to the same side. How to refine the approximation? search for a pair of values one from each list that most closely differ by half the difference between the two totals. Now swap them and repeat the process until you have the two total sufficiently balanced. ------------------- Alf P.Steinbach wrote: Never compare floating point numbers for equality (regardless of programming language). They will almost never be equal. Rough explanation of that: a floating point number is (can be regarded as) internally represented by three integers S, M and E, where the sign S is +1 or -1, the mantissa M represents the digits, using a fixed number of binary digits, and the exponent E represents the placement of the radix point. The value then being S*M*(2^E). For example, the number 1.2 *can not* be exactly represented in this way, because there's no way to choose M and E so that M*2^E yields exactly 1.2; instead what you get is a representation that is very close to 1.2. And two floating point numbers may even compare unequal when they're computed by the same expression from same argument values. Ironically this last pitfall, if present, is due to an attempt to improve the accuracy of floating point arithmetic results, by using "extended precision". ------------------ Jonathon Campbell wrote: Maybe it is time to move on from that problem? I admire your determination, and determination is something required to learn how to program, but maybe you can benefit from moving on to the next chapter? And mark the exercise as something to return to? To be honest, the learning objective of that exercise has not been clear to me, at least as an exercise in Chapter 3 of an introductory textbook. If your were working in a lab. with a teacher, I'd expect the teacher to occasionally warn you that you are in a cul-de-sac and to give a hint on how to proceed. But you are not getting that sort of assistance and you could be at it forever and possibly learning bad habit along the way --- yes, that's what I'm most concerned about, that you will need to attempt tasks that your stage in the book has not prepared you for. Ben Bacarisse wrote: There is no guarantee that your algorithm can solve the problem (and in fact it can't). As far as I can tell, not even the algorithm proposed by the author of the problem will not solve it (to the accuracy required). I think the previous poster has point. This is a very hard exercise and I would suggest you come back to it later. I stumbled on a solution but it is one that does not generalise. The general problem of finding a subset of some set of numbers (of any size) that is arbitrarily close to some given value (in this case half the total) is what is called NP-complete. Solving such problems usually requires something close to searching the full solution set for the best answer (I am not being technically correct here, please forgive this lax presentation). For a set of N numbers that are 2**N subsets to check. Swapping pairs will never try all of these. ---------------- This was the flawed attempt I made to solve this problem. It runs, but it does not work: // separates ints 1 to 100 into two sets // the sum of the square roots of both sets // will be equal to six significant digits #include #include #include #include #include double closestnumber(double, std::vector); int main() { std::vector set_a; std::vector set_b; const double range_low(335.7310); const double range_high(335.7319); double totalset_a(0); double totalset_b(0); for (int i = 0; i < 100; ++i) { if (i % 2 == 0) { set_a.push_back(sqrt(i)); totalset_a += sqrt(i); } else { set_b.push_back(sqrt(i)); totalset_b += sqrt(i); } } std::cout << "Total of Set A is initially " << totalset_a << '\n'; std::cout << "Total of set B is initially" << totalset_b << '\n'; bool end = false; do { double differenceinsets(0); double halfdiff(0); differenceinsets = totalset_a - totalset_b; halfdiff = differenceinsets / 2; double close(0); close = closestnumber(halfdiff, set_a); int tempApos(0); for (size_t i=0; i<=set_a.size(); ++i) { if (set_a[i] == close) { tempApos = i; } } close = closestnumber(halfdiff, set_b); int tempBpos(0); for (size_t i=0; i<=set_b.size(); ++i) { if (set_b[i] == close) { tempBpos = i; } } /*double hold = set_a[tempApos]; set_a[tempApos] = set_b[tempBpos]; set_b[tempBpos] = hold; */ if(totalset_a < range_low) { // put some values into set a double hold = set_b[tempBpos]; set_a.push_back(hold); set_b[tempBpos] = 0; } else { double hold = set_a[tempApos]; set_b.push_back(hold); set_a[tempApos] = 0; } std::sort(set_a.begin(), set_a.end()); std::sort(set_b.begin(), set_b.end()); totalset_a = 0; std::cout << "SET A: \n"; for (size_t i=0; i<=set_a.size(); ++i) { std::cout << set_a[i] << '\n'; totalset_a += set_a[i]; std::cout << "Total set A is " << totalset_a << '\n'; } totalset_b=0; std::cout << "SET B: \n"; for (size_t i=0; i<=set_b.size(); ++i) { std::cout << set_b[i] << '\n'; totalset_b += set_b[i]; std::cout << "Total set B is " << totalset_b << '\n'; } std::cout << "Total set A is " << totalset_a << '\n'; std::cout << "Total set B is " << totalset_b << '\n'; if (totalset_a >= range_low && totalset_a <=range_high) { end = true; } } while (end != true); } // end of main double closestnumber(double halfofdiff, std::vector dataset) { double difference(0); double smallestdifference(10); double closestvalue(0); for (size_t i=0; i <= dataset.size(); ++i) { difference = halfofdiff - dataset[i]; difference = sqrt(pow(difference, 2)); if (difference < smallestdifference) { smallestdifference = difference; closestvalue = dataset[i]; } } return closestvalue; } -------------------- In tackling this again, I will need to: 1. Be clear about the correct algorithm to solve it. I was not able to construct an algorithm myself. I relied on a general statement made by the author. Unfortunately, it seems that I misinterpreted what the actual algorithm is supposed to do. Alf P. Steinbach noted that: > Ben Bacarisse wrote: > >> Note that this is not the algorithm proposed by the author (unless I >> miss-read it). Picking a pair, each of which is close to half the >> difference, is not the same as picking the pair that differ by an >> amount close to half the difference! > > > I dont understand this. Can you explain this please? The basic step in the algorithm is to reduce the difference between the (sums of the) sets. If every successful iteration reduces the difference then the algorithm can't make things worse, and just may make things better -- wrt. the goal. If you could find a pair of numbers, one from each set, whose difference was exactly half the difference of the sums of the sets, *with the larger of those numbers residing in the set with the largest sum*, then you could just swap them and you would have an exact solution. But generally there will be no such pair of numbers. So the proposed algorithm is to instead search for a pair that is as close as possible to that, swap, search again, and so on, until some measure of progress drops below some threshold. --------------- So unfortunately, for the time being, I will have to leave this problem.