Started to learn recursion and I am stuck with this simple problem. I believe that there are more optimized ways to do this but first I'm trying to learn the bruteforce approach.
I have bag A and bag B and have n items each one with some time (a float with two decimal places). The idea is to distribute the items by the two bags and obtain the minimum difference in the two bags. The idea is to try all possible outcomes.
I thought only in one bag (lets say bag A) since the other bag will contain all the items that are not in the bag A and therefore the difference will be the absolute value of total times sum - 2 * sum of the items time that are in the bag A.
I'm calling my recursive function like this:
min = total_time;
recursive(0, items_number - 1, 0);
And the code for the function is this:
void recursive(int index, int step, float sum) {
sum += items_time[index];
float difference = fabs(total_time - 2 * sum);
if (min > difference) {
min = difference;
}
if (!(min == 0.00 || step == 1 || sum > middle_time)) {
int i;
for (i = 0; i < items_number; i++) {
if (i != index) {
recursive(i, step - 1, sum);
}
}
}
}
Imagine I have 4 items with the times 1.23, 2.17 , 2.95 , 2.31
I'm getting the result 0.30. I believe that this is the correct result but I'm almost certain that if it is is pure change because If I try with bigger cases the program stops after a while. Probably because the recursion tree gets to bigger.
Can someone point me in some direction?
Okay, after the clarification, let me (hopefully) point you to a direction:
Let's assume that you know what n is, mentioned in n items. In your example, it was 2n is 4, making n = 2. Let's pick another n, let it be 3 this time, and our times shall be:
1.00
2.00
3.00
4.00
5.00
6.00
Now, we can already tell what the answer is; what you had said is all correct, optimally each of the bags will have their n = 3 times summed up to middle_time, which is 21 / 2 = 10.5 in this case. Since integers may never sum up to numbers with decimal points, 10.5 : 10.5 may never be achieved in this example, but 10 : 11 can, and you can have 10 through 6.00 + 3.00 + 1.00 (3 elements), so... yeah, the answer is simply 1.
How would you let a computer calculate it? Well; recall what I said at the beginning:
Let us assume that you know what n is.
In that case a naive programmer would probably simply put all those inside 2 or 3 nested for loops. 2 if he/she knew that the other half will be determined when you pick a half (by simply fixing the very first element in our group, since that element is to be included in one of the groups), like you also know; 3 if he/she didn't know that. Let's make it with 2:
...
float difference;
int i;
for ( i = 1; i < items_number; i++ ) {
sum = items_time[0] + items_time[i];
int j;
for ( j = i + 1; j < items_number; j++ ) {
sum += items_time[j];
difference = fabs( total_time - 2 * sum );
if ( min > difference ) {
min = difference;
}
}
}
...
Let me comment about the code a little for faster understanding: On the first cycle, it will add up the 0th time, the 1st time and then the 2nd time as you may see; then it will do the same check you had made (calculate the difference and compare the it with min). Let us call this the 012 group. The next group that will be checked will be 013, then 014, then 015; then 023, and so on... Each possible combination that will split the 6 into two 3s will be checked.
This operation shouldn't be any tiresome for the computer to issue. Even with this simple approach, the maximum amount of tries will be the amount of combinations of 3 you could have with 6 unique elements divided by 2. In maths, people denote this as C(6, 3), which evaluates to (6 * 5 * 4) / (3 * 2 * 1) = 20; divided by 2, so it's 10.
My guess is that the computer wouldn't make it a problem even if n was 10, making the amount of combinations as high as C(20, 10) / 2 = 92 378. It would, however, be a problem for you to write down 9 nested for loops by hand...
Anyway, the good thing is, you can recursively nest these loops. Here I will end my guidance. Since you apparently are studying for the recursion already, it wouldn't be good for me to offer a solution at this point. I can assure you that it is do-able.
Also the version I have made on my end can do it within a second for up to items_number = 22, without having made any optimizations; simply with brute force. That makes 352 716 combinations, and my machine is just a simple Windows tablet...
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments