Finding amounts that adds up to another amount

Comments

• CyGuy

  September 2005

  [b][red]This message was edited by CyGuy at 2005-9-26 19:17:54[/red][/b][hr]
  [b][red]This message was edited by CyGuy at 2005-9-19 5:26:11[/red][/b][hr]
  :
  : I have a target amount, and a list of amounts. One of the amounts in the list or a sum of amounts from the list, 2,3 or more of the amount can match the target amount. How do you suggest that I search for a match?
  :
  try using a subroutine/function... or modular algorithm
  
• Lazarus404

  October 2005

  [b][red]This message was edited by Lazarus404 at 2005-10-6 2:10:33[/red][/b][hr]
  : [b][red]This message was edited by CyGuy at 2005-9-26 19:17:54[/red][/b][hr]
  : [b][red]This message was edited by CyGuy at 2005-9-19 5:26:11[/red][/b][hr]
  : :
  : : I have a target amount, and a list of amounts. One of the amounts in the list or a sum of amounts from the list, 2,3 or more of the amount can match the target amount. How do you suggest that I search for a match?
  
  Work on a loop. First, match 2 numbers going from item 1 with each respective item, then item 2 etc through all numbers, then try 3 an 4 etc... You could do this with bits, like this
  
  int value = 10;
  int list() = {5, 7, 3, 2, 9, 4, 4};
  const int bits() = {1, 2, 4, 8, 16, 32, 64}; //Same number of bit values as items in the list.
  for (int counter = 0; counter<=127; counter++) // should probably find out what the total number is for all bits in a function
  {
  int numItems = 0;
  int total = 0;
  for (int i=0; i<bits.length; i++)
  {
  if (bits[i] & counter == bits[i])
  {
  total += list[i];
  numItems++;
  }
  }
  if (total = value)
  {
  break;
  }
  }
  int newList(numItems);
  int item = 0;
  for (int i=0; i<bits.length; i++)
  {
  if (bits[i] & counter == bits[i])
  {
  newList[item] = list[i];
  item++;
  }
  }
  
  // newList should now contain all the items necessary to make up your new value.