Announcement

Collapse
No announcement yet.

How to determine if any combination of values combined will equal a target value?

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

    How to determine if any combination of values combined will equal a target value?

    I have 12 values.
    I need to somehow check every combination of those 12 values to see if any combination of them will equal a target number.
    For instance,
    Target=500
    I have 12 Random Numbers that are divisible by 5
    If there is no combination of those numbers that add up to 500, trigger event.
    I have no idea how to do this so I am just guessing.
    I have an array that has the 12 values stored.
    I then use a for each loop that takes the first value and then adds each of the other values in the array to it. If at any point it equals the target, trigger event.
    If it doesn't find a solution in with the first value it moves on to the next for loop.
    This time I add the first value and the second value then I run that through the loop to add the rest of the values to get an outcome.
    Only problem is that it adds values that dont need to be added.
    If Value 1 is added to each other value, it also adds value 1 to value 1. Because the for loop does each value in the array. How would I bypass
    certain values in the loop. For instance, if I dont find a solution to the first value, I will also need to bypass the first and second value then next time it loops.
    My brain hurts.

    #2
    I am typing this on my phone so it might be messy. Basically what you want is a fairly advanced algorithm. What I have in mind is probably not the most optimal solution and I suggest poking around google for closest sum algorithms. Now...

    You have 12 values and want to get a total of 500... You take an empty bucket (0) and start "pouring" your numbers in. First of all remove any numbers that are greater than 500. Then start with the largest one that fits and keep adding in smaller numbers until you either get 500 or the next number you add exceeds 500.

    Now this is where you run into the problematic part. Question is now if you can replace any of the existing bigger numbers in your bucket with a combination of smaller ones to match 500.

    Say for the sake of the argument that at this point you have 496 in your bucket so you need to add in 4 to complete it, but all of your remaining numbers are > 4.

    First of all, you know that every number in your bucket is greater than every number outside since you added them in decreasing order. The first step is checking each number outside your bucket and seeing how much it would overshoot. Then, for each of those compare your other outside numbers with your bucket numbers and see if any of them is smaller by the overshoot amount. If it is then you can just swap them and your overshoot number will now fit perfectly.

    This can be optimized somewhat by doing the "does the difference match the overshoot" check in increasing order, i.e. for each outside number start checking from the smallest bucket number and work upward to the largest one... Keep going as long as their difference is.smaller than the overshoot. If it... overshoots the overshoot you can move on to the next outside number.

    Now, if THIS doesn't yield the result there remains the possibility that by adding the outside numbers you can get one that fits in. This is where things get real tricky.

    What you need to do is check is start adding up the outside numbers, run the whole thing from the top with the new sum being treated as one number. You do this recursively with each 2, 3, 4... n number addition of outside numbers.

    Each iteration level should continue if their closest match is closer than the previous ones. It should return if the match is <= than the current best. If all the "additions" return then you can't make your addition.

    Now that I've typed it all out I do not believe this to be the most optimal solution. I'll give it some more thought and get back to you.

    EDIT:
    Ok a small google search confirmed that this is essentially the knapsack problem. This is the solution:

    There are several ways to solve subset sum in time exponential in N. The most naïve algorithm would be to cycle through all subsets of N numbers and, for every one of them, check if the subset sums to the right number. The running time is of order O(2NN), since there are 2N subsets and, to check each subset, we need to sum at most N elements.

    A better exponential time algorithm is known which runs in time O(2N/2). The algorithm splits arbitrarily the N elements into two sets of N/2 each. For each of these two sets, it stores a list of the sums of all 2N/2 possible subsets of its elements. Each of these two lists is then sorted. Using a standard comparison sorting algorithm for this step would take time O(2N/2N). However, given a sorted list of sums for k elements, the list can be expanded to two sorted lists with the introduction of a (k + 1)st element, and these two sorted lists can be merged in time O(2k). Thus, each list can be generated in sorted form in time O(2N/2). Given the two sorted lists, the algorithm can check if an element of the first array and an element of the second array sum up to s in time O(2N/2). To do that, the algorithm passes through the first array in decreasing order (starting at the largest element) and the second array in increasing order (starting at the smallest element). Whenever the sum of the current element in the first array and the current element in the second array is more than s, the algorithm moves to the next element in the first array. If it is less than s, the algorithm moves to the next element in the second array. If two elements with sum s are found, it stops. Horowitz and Sahni first published this algorithm in a technical report in 1972.
    An alternative solution and more info here: http://en.m.wikipedia.org/wiki/Subset_sum

    Edit 2:
    A code solution (both slow but simple and less slow but more complex) found here:http://www.geeksforgeeks.org/dynamic...t-sum-problem/
    Last edited by DamirH; 05-07-2015, 09:30 PM.

    Comment


      #3
      Dedrick, but he wants to know if any combination = 500, not if all of them added are 500.
      Marketplace Assets

      Advanced Mobile Input: Marketplace Page | Support Thread ――― Easy Input Remapping: Marketplace Page | Support Thread
      Multiplayer Blueprint Chat System: Marketplace Page | Support Thread ――― Closing Credits System: Marketplace Page | Support Thread
      Minesweeper Template: Marketplace Page | Support Thread ――― Maze Creator: Marketplace Page | Support Thread

      Comment


        #4
        *EDIT* Hmm, I misread the original post. Disregard
        Last edited by DEDRICK; 05-07-2015, 10:46 PM.

        Comment


          #5
          Make sure you read my previous post dedrick, this is adding 1, 2, 3 , 4, etc... Until it == 500, but what if index 3 + 7 == 500? This is what he is trying to do.
          Marketplace Assets

          Advanced Mobile Input: Marketplace Page | Support Thread ――― Easy Input Remapping: Marketplace Page | Support Thread
          Multiplayer Blueprint Chat System: Marketplace Page | Support Thread ――― Closing Credits System: Marketplace Page | Support Thread
          Minesweeper Template: Marketplace Page | Support Thread ――― Maze Creator: Marketplace Page | Support Thread

          Comment


            #6
            This is not an easy problem and definitely not something to be done in BP.

            Comment


              #7
              James, could you tell us why you need to find this? And what are you doing that requires this? I might know of a better solution.
              Marketplace Assets

              Advanced Mobile Input: Marketplace Page | Support Thread ――― Easy Input Remapping: Marketplace Page | Support Thread
              Multiplayer Blueprint Chat System: Marketplace Page | Support Thread ――― Closing Credits System: Marketplace Page | Support Thread
              Minesweeper Template: Marketplace Page | Support Thread ――― Maze Creator: Marketplace Page | Support Thread

              Comment


                #8
                I was trying to do a simple math game. So there's 12 blocks on the board, each with a number that is divisible by 5. I set a target value and give the player a small window of time to click numbers and add until they hit the target value. But I need it so when the player miscalculates, the game knows there is no other combination that will equal the target value.
                For instance, your current value is at 75, the target is 100, and there are 3 blocks left and none of them are 25 or can equal 25. So its impossible for you to hit the target. The way it is now, you already know you lost but you have to go ahead and just choose a block so the game resets.
                So the board would have to be able to calculate all remaining values and determine if there is a solution.

                Comment


                  #9
                  Hello,
                  At least a quick way to check is to make an array with your values, you loop, add the array element to other array element (by a second loop) and check if result is = your value

                  Edit : by this way, you can store the results too and choose one to always have a reachable goal.

                  Comment


                    #10
                    Well, if you want to check all future turns, it will be hard. If you just check the remaining solutions each turn, it will be very easy. Just check to see whether any of the solutions added to current number are the goal. There aren't any simple answers to check all future turns though.
                    Marketplace Assets

                    Advanced Mobile Input: Marketplace Page | Support Thread ――― Easy Input Remapping: Marketplace Page | Support Thread
                    Multiplayer Blueprint Chat System: Marketplace Page | Support Thread ――― Closing Credits System: Marketplace Page | Support Thread
                    Minesweeper Template: Marketplace Page | Support Thread ――― Maze Creator: Marketplace Page | Support Thread

                    Comment


                      #11
                      Just do the dynamic programming algorithm suggested in this link: http://www.geeksforgeeks.org/dynamic...t-sum-problem/

                      Run this at the start to determine whether a combination exists. If it does the numbers are solid. The second dynamic programming algorithm there works great for determining whether a combination exists, if not necessarily to find it. Note that the complexity of the algorithm depends on how big the number you're looking for is. And since all of your numbers are multiples of 5, you can divide everything by 5 before running it through the algorithm and you'll get your result.

                      Comment


                        #12
                        I am trying to understand how to do this in Blueprints. I have the array of all my values and I can add them together using the for loop. But I don't know how to bypass certain array elements. For instance, with only 3 values, I take the first value, in this case I'm using get from the array with the index at 0, plugging it into an int + int, using a for loop and plugging the array element in the top of the int+int. It will add 1+1, 1+2, 1+3. Which works, but I don't need to add 1+1. And with a higher number of values I will need to bypass many parts of the array because certain values will not need to be added to themselves. In the dynamic programming link I read that they are taking the number of index's in the array and subtracting by 1. This is the part I am unsure how to do.

                        Comment

                        Working...
                        X