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)

2 Likes

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

Log n (x) ?