Reach a variable number with the sum of fixed numbers

Hello guys
I would like to aks your help, I’d like to make a grasshopper program which helps to solve my problem, i don’t know python/C#/VB coding that’s why I ask your help.
The problem is the following (It’s a bit similar to the Knapsack problem):
I have a Variable --> X
and
I Have fix numbers (can we call “pieces”) 9,12,15,18
I’d like to reach the X, with the summing of these numbers and using the minimum pieces ,it CAN’T be lower than X, but it can be higher, maximum with 3.
After this it has to found the most optimal combination which mostly use the same pieces

E.G.
X=98
The wrong solution is like = 1pcs of 18 + 9pcs of 9 =99
Sum of pieces are 10
OR
3pcs of 18 + 1pcs of 15 +1pcs of 12 +2pcs of 9 = 99
Sum of pieces are 7

The right solution in this case = 5pcs of 18 + 1pcs of 9 =99
it’s good beacuse it’s over with maximum 3 and uses the minimum pieces

Then it sends to a list like
18 : 5pcs
15 : 0pcs
12 : 0pcs
9 : 1pcs
Can somebody help me ? Or is it possible to make this ?
Thank you!

Replied with one potential approach here.

The problem is that there’s no algorithm for creating this series that doesn’t require backtracking. The most obvious one is to repeat the largest value as often as possible, but then you may be left with a gap which cannot be filled with any of the remaining pieces. In fact given certain inputs, a solution may not even be mathematically possible. Grasshopper is not good at implementing recursive/backtracking algorithms, it likes a simple, linear workflow.

The alternate approach is to generate all the sequences that may have a possibility of being correct and pick the best one. That might work for some cases, but here I fear that the set of all possible sequences (even after removing obviously bad ones) is probably far too large.

So yes, @AndersDeleuran’s solution which uses custom scripting is one way around this, and may be the only way around this.

Here’s a C# approach which does everything from scratch. There’s a lot of code in there, and it’s pretty complicated. I have no proof that it will find the best sequence (I think it will, but I could be wrong), I have no proof that it will not get stuck recursing forever (I think it won’t, but I could be wrong).

setpieces.gh (14.6 KB)

3 Likes

It’s fine, I appreciate your help thank you :slight_smile:

Log n (x) ?

Hi David, thank you for the code!
Can you please explain, how to take into account, amount of each pieces, to compute solution from available pieces?

Would be really appreciate for your help!

Until David’s explanations … this is a rather “over simplistic” take on that puzzle (i.e. given a List of nums find all combos where sum is > min and < max). Note: no “post action” Method is included (but that’s rather simple).


1 Like

It’s Sunday evening, so I’m not going to do the boring thing and read my old code, I’m just going to try and remember it.

You start adding together the biggest element until you hit or overshoot the target number. If you hit it; hey presto! If you overshoot; remove the last element from the summation list and start adding copies of the second largest element until you hit or overshoot. Keep repeating until you’ve overshot using the smallest element. If you still don’t have a solution, then you must recurse all the way back to the beginning and remove another instance of the largest element.

Elements in order from smallest to largest: (5, 7, 10, 22)
Target: 99

  1. 22 + 22 + 22 + 22 + 22 = 110
  2. remove the last 22, then start adding 10s until the next overshoot happens.
  3. 22 + 22 + 22 + 22 + 10 + 10 = 108
  4. remove the last 10, then start adding 7s until we overshoot again.
  5. 22 + 22 + 22 + 22 + 10 + 7 = 105
  6. remove the last (and only) 7, then start adding 5s.
  7. 22 + 22 + 22 + 22 + 10 + 5 = 103
  8. 5 is the smallest element, so we need to remove all 5s as well as the previous number (i.e. 10), then start adding again.
  9. 22 + 22 + 22 + 22 + 7 + 7 = 102
  10. 22 + 22 + 22 + 22 + 7 + 5 = 100
  11. 22 + 22 + 22 + 22 + 5 + 5 + 5 = 103
  12. 22 + 22 + 22 + 10 + 10 + 10 + 10 = 106
  13. 22 + 22 + 22 + 10 + 10 + 10 + 7 = 103
  14. 22 + 22 + 22 + 10 + 10 + 10 + 5 = 101
  15. 22 + 22 + 22 + 10 + 10 + 7 + 7 = 100
  16. 22 + 22 + 22 + 10 + 10 + 7 + 5 + 5 = 103
  17. 22 + 22 + 22 + 10 + 10 + 5 + 5 + 5 = 101
  18. 22 + 22 + 22 + 10 + 7 + 7 + 7 + 7 = 104
  19. 22 + 22 + 22 + 10 + 7 + 7 + 7 + 5 = 102
  20. 22 + 22 + 22 + 10 + 7 + 7 + 5 + 5 = 100
  21. 22 + 22 + 22 + 10 + 7 + 5 + 5 + 5 + 5 = 103
  22. 22 + 22 + 22 + 10 + 5 + 5 + 5 + 5 + 5 = 101
  23. 22 + 22 + 22 + 7 + 7 + 7 + 7 + 7 = 101
  24. 22 + 22 + 22 + 7 + 7 + 7 + 7 + 5 = 99 Yay!

Very tedious to do by hand…

2 Likes