Finding amounts that adds up to another amount - Programmers Heaven

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Finding amounts that adds up to another amount

aEvaaEva Posts: 1Member

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?

Comments

  • CyGuyCyGuy Posts: 312Member
    [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
  • Lazarus404Lazarus404 Posts: 15Member
    [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.


Sign In or Register to comment.