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.
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:
An alternative solution and more info here: Subset sum problem - Wikipedia
Edit 2:
A code solution (both slow but simple and less slow but more complex) found here:Dynamic Programming - Subset Sum Problem
Dedrick, but he wants to know if any combination = 500, not if all of them added are 500.
EDIT Hmm, I misread the original post. Disregard
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.
This is not an easy problem and definitely not something to be done in BP.
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.
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.
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.
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.
Just do the dynamic programming algorithm suggested in this link: Dynamic Programming - Subset 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.
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.