Using Arrays to find a target value.

[wwepensync]

Hello everyone, I am beginner in C programming, so bear with me if my code is horrendous.

I wanted to write a program that will determine a set of values that add up to a target value. I want to use 12 bins and fill the bins with random numbers between 0 and 20. Then, look for a target value of 30.

Here is what I have so far. (mix of actual code and Pseudocode.) I have the basic idea of what to do, just am lost on how to fill/print in Bins properly as I have never used them before. I am beginner in C programming, so bear with me if my code is horrendous.

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <conio.h>
#include <stdlib.h>

int main (void)
{

// columns: 0=value  1=checked  2=selected
int bins[BINCOUNT][3];

   fillbins();
   
   /* 
   Search for max unselected value and mark it as checked.
   Then, if it will fit into the sum, mark it as selected.
   */

   do{
      r = findmax();   // find next largest unchecked value
      bins[r][1] = 1;  // mark this row as checked
            
      // can we used this value?
      if sum + bins[r][0] less than TARGETWEIGHT
      {
         // add this value to sum
         // mark this row as selected
      }
      
      printbins();      
      // also print other info as req'd
      // increment count
   } while sum less than TARGETWEIGHT and count < BINCOUNT
}

Sample Output

 i   v   c   s
 0  14   0   0
 1  12   0   0
 2   0   0   0
 3   6   0   0
 4  12   0   0
 5   9   0   0
 6  15   1   1
 7  15   0   0
 8   9   0   0
 9   2   0   0
10   0   0   0
11   8   0   0

Next largest value is 15 found at location 6
Value selected
Sum is 15. count is 0

 i   v   c   s
 0  14   0   0
 1  12   0   0
 2   0   0   0
 3   6   0   0
 4  12   0   0
 5   9   0   0
 6  15   1   1
 7  15   1   1
 8   9   0   0
 9   2   0   0
10   0   0   0
11   8   0   0

Next largest value is 15 found at location 7
Value selected
Sum is 30. count is 1

Final Solution: 
  i   v 
  6  15
  7  15

Sum: 30
Press any key to continue . . . 

[Duthomhas]

If I understand it properly, for each bin you want to see if it contains a subset of numbers that add to the target?

(For example: given a bin of 1 9 3 2 3, can you get a sum of 7?)

If that is the case, a greedy algorithm will not necessarily help you.

(For example: given a bin of 2 3 2, can you get 4? Not if you choose 3 first.)

[wwepensync]

Yes, exactly. But thats why i want it to check each bin and select all possible locations to see if they add up to 30.

(For example, if you look at my sample output: given a bin of, 14 12 0 6 12 9 15 15 9 2 0 8, it should be able to recognize that 12 + 12 + 6 can also = 30 and is a plausible way to come up with the target value.)

That way, shouldn't that eliminate the problem with choosing the largest number all the time?

[Duthomhas]

No, because it is possible to check/select values that add up to something that is too big to be used with the remaining values. Unless there is a way to consistently uncheck/unselect a value then the algorithm cannot proceed.

Your algorithm looks for the largest value next, so it can never select 12 as a first value, hence it cannot find 12 + 12 + 6.

The same problem occurs if you start with the smallest values. Unless you have a way of backtracking and choosing a different branch then you cannot find a path to the proper end.

You might want to look at combinations. The STL provides the handy std::next_permutation() function so you can modify your bins until you get an initial sequence that sums to your target value.

Then you also only need to have numbers in your bins (and not checked/selected stuff).

Hope this helps.