Finding combination of numbers

[zakariarahman]

i have a labview vi which will generate a number. Then I have a 1D array where there will be some numbers value. 

For example lets say my vi generates 4.75 and the array looks like

0.1

0.2

0.5

0.7

0.9

1

2

3

4

5

6

Now the program should check the array and select the closed combination which will give me 4.75.

so for example selecting 4, 0.7 and 0.1 gives me 4.8 which is close to 4.75 or selecting 4+0.7. IS there a way to achieve this in labview.

Thnak you very much

[GerdW]

Hi zaka,

---

@zakariarahman wrote:

IS there a way to achieve this in labview.

---

Yes!

Spoiler

Sketch your algorithm on a sheet of paper. Then implement it in LabVIEW!

[Bob_Schor]

Ah, a Classic Problem in computing and combinatorics.  I believe this problem (a.k.a. the K-----ck Problem) is NP-Complete.

Bob Schor

[Yamaeda]

Something like: Find the 1st number that's bigger than the target, that's the starting point and comparison and we can cut the list there as we know it can never be anything after that number. In your example, the number list can never include anything larger than 5.

Then, as mentioned, it's a NP problem. You need to create a list of all other possibilities and compare the error with your current best list (which start with the 1 element list '5'). You can be smart and stop the comparison once a lists total is larger than the current best list.

Good luck.

[altenbach]

---

@zakariarahman wrote:

Now the program should check the array and select the closed combination which will give me 4.75.

so for example selecting 4, 0.7 and 0.1 gives me 4.8 which is close to 4.75 or selecting 4+0.7.

---

Of course 4, 0.7, (=4.7) would be equally close to 4.75. With your input set, the problem will be quite simple, but it could be arbitrarily complex if the set of values is more random. You could have a set of numbers where every sum of picks gives a different result.

You also need to define the problem better:

• Can you re-use each value from the set more than once?
• Most likely there is more than one solution. Are there additional constraints (smallest number of picks? The value below if there is a tie? etc.)

---

@zakariarahman wrote:

IS there a way to achieve this in labview.

---

This is not a LabVIEW problem. But once you figure out an algorithm, you can implement it in any programming language, including LabVIEW. 😄

[zakariarahman]

i am trying to implement it but unfortunately finsing it a bit difficult. An example program would have greatly helped.

Thanks for explaining 🙂

[altenbach]

We cannot really help until you define the problem fully. Do you have answers to some of my questions?

If this is too difficult, first try to solve a few simpler problems.

[zakariarahman]

Sorry for the delayed reply. to answer your question:

1. I wont be able to reuse the value from the set more than once

2. And i will set a tolerance to how close the sum has to be to the exact number. If I don't find any combination its okay i will just say no combinations found.

What i was thinking was a code that will take the array and already make an array of all summation possible. Then check which values of summation gets closest to my input number, it should be a @d array because I want to see too what numbers were added from the list to get the desired summation. and then select the closest one to my summation which has the least number of elements. So according to my example I would prefer to take the 4, .07 combination then the 4, .07, 0.1. 

Thank you again for replying and helping 🙂

[GerdW]

Hi zakaria,

---

@zakariarahman wrote:

What i was thinking was a code that will take the array and already make an array of all summation possible.

---

This "array of all summation" will get very large very soon: are you sure you really want to create all possible combinations?

---

@zakariarahman wrote:

it should be a @d array because I want to see too what numbers were added from the list to get the desired summation.

---

So this "array of all summation" will get even larger because you also want to store all elements for each sum?

Have you started to draw your algorithm on a sheet of paper? Can you attach a picture of that drawing?