1
$\begingroup$

I'm trying to design an algorithm for evenly fitting decimal numbers into a decimal number.

Say I have a set $N$ of decimal numbers ($N_1$, $N_2$, ..., $N_n$) and a target value $Y$. I'd like to see what combination of values of $N$ (values may be used zero to many times) add up evenly to $Y$.

I've accomplished it by selecting random values of $N$ until I either add up to $Y$ or pass it - at which point I start over. This algorithm does not seem efficient, however. Sometimes it takes 50k passes before it lands on an answer.

The set I'm actually working with is 21 dollar values between \$0.89 and \$8.04 and the target is \$43.94.

Is there a simpler algorithm?

|cite|improve this question
$\endgroup$
  • $\begingroup$ One thought I had is that I can add up to approximately the target and then attempt to replace numbers in the set with others that are more or less. If I'm say 0.02 below my target then I look for items in my set that can be replaced by items that cost 0.02 more. $\endgroup$ – Jeremy Foster Nov 17 '18 at 4:14
  • $\begingroup$ Are these integers? If so, you can use the extended Euclidean algorithm. Can you edit the question to clarify what you mean by "decimal numbers"? $\endgroup$ – D.W.♦ Nov 17 '18 at 4:49
  • $\begingroup$ Can you describe a trivial example and a simple nontrivial example in the question? If you can share your algorithm on some online IDE such as repl.it, that would be useful for the potential answerers, too. $\endgroup$ – Apass.Jack Nov 17 '18 at 5:11
  • $\begingroup$ How large are your numbers? $\endgroup$ – Yuval Filmus Nov 17 '18 at 5:46
  • $\begingroup$ Added information to my question to clarify the set I'm working with. $\endgroup$ – Jeremy Foster Nov 17 '18 at 15:27
1
$\begingroup$

Provided the $N_i$ are all positive, this is pretty much exactly the problem of "how many ways can I make value $Y$ out of coins with values $N_i$ (assuming no restriction on the number of coins)?"

That problem has a very easy recursive solution that breaks into two cases at each step:

  1. Include a "coin" of value $N_i$ and recurse.
  2. Assume you have used $N_i$ as many times as you are willing and recurse using only values $N_j$ for $j > i$.
|cite|improve this answer
$\endgroup$
  • $\begingroup$ The coin values always go all the way down to \$0.01, so you're assured of being able to land on $Y$. In my problem, the set $N$ doesn't necessary contain a value of \$0.01, so it's possible there is no solution for a given problem. Check me here. $\endgroup$ – Jeremy Foster Nov 21 '18 at 19:05
  • $\begingroup$ I don't really see why it should matter if the values go to $0.01 or not. In the case you can't complete the value Y, there are simply 0 ways to do it, and you just drop the combination upon realizing this. $\endgroup$ – Sebastian Nov 29 '18 at 3:18
  • $\begingroup$ Good point. I don't totally understand your pseudocode, though. In step 1, what precisely do you mean by "recurse"? Do you mean to add the same $N$, the next $N$? You say to use $N_i$ "as many times as you are willing". In my problem, each value of $N$ can be used without constraint. So it seems to me that strictly following your logic I would take either the first or a random $N_i$ and continue adding it to the proposed solution set until it didn't work. Then how would I proceed to attempt a new set? $\endgroup$ – Jeremy Foster Nov 30 '18 at 4:36
  • $\begingroup$ I'm assuming you can order the $N_i$. You start with $i = 1$, and break into two cases: 1. Add another $N_1$ (if possible, i.e. this won't surpass the target $Y$) and recurse to try to form target $Y' = Y - N_1$, or 2: Investigate the solution where we are not using any more $N_1$, i.e. try to form $Y' = Y$ out of $N_2, N_3, ...$. I'll try to improve my pseudocode today to make it clearer. $\endgroup$ – Sebastian Nov 30 '18 at 9:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.