Any subset sum calculator that considers multiplication? [clarified]

[Eglaios]

I'm searching for some code that would allow me to do the following :
(it's just for myself to check values, I only need to use this alone)

[EDIT] Rules :
1. User inputs an array of @numbers, and a @goal
2. The code searches for sums of @numbers that would match @goal value, following these rules :
--The only operation allowed to combine @numbers is sum
--There could be any amount of the same @number involved in sums
--If @goal can't be matched, returns the closest sum available
--[optional] Could work with negative @numbers

Example 1 - Exact goal reached :
-Input :

Code: Select all

{numbers = {1,2,3}, goal=3}

Returns :

Code: Select all

Found 3 matches :
numbers[1]*3
numbers[1]*1 + numbers[2]*1
numbers[3]*1

Example 2 - Goal can't be reached:

Code: Select all

{numbers = {1,2,3}, goal=3.1}

Returns :

Code: Select all

No match found, closest match = 3 :
numbers[1]*3
numbers[1]*1 + numbers[2]*1
numbers[3]*1

(I'd like it to be compatible with negative numbers as well, if possible, and display the closest obtainable value if there's no exact result)

The only calculators I found only took each number once per sum, though I want them to be able to consider more than one of the same number per sum (of course, for this, there needs to be a searching range limit, otherwise the thing would go "3 = 1*1000003 + -2*500000" up to infinity)

I would mainly want to compare arrays containing ~ 20 float numbers between -10 and 10, so I wouldn't need a huge amount of memory for that...


(I hope it's more clear now...)

[pgimeno]

I don't understand the rules. You say you want a subset sum (I presume is what you mean) but with multiplication, and I don't get what multiplications should be valid. One way to understand it is similar to a TV contest where contestants need to get as close as possible to a given number, by using only a set of numbers and using the four classic arithmetic operators on them. But in your example, you use 1*1 + 2*1 which uses the 1 three times, and that's against the rules of the contest, so that's not it.

Can you clarify?

[darkfrei]

Code: Select all

target_n = 3
for i =  1, 10^6 do
	local str = ""
	str = str .. any_number () -- returns number
	for j = 1, 3 do
		str = str .. any_operator () -- returns operator: +, -, *, /
		str = str .. any_number ()
	end
	print (str)
	local n = calculate (str) -- calculates the str as calculator
	if n == target_n then return end
end

Every of them can be stored index of first number, index of first operator, index of second number etc.

Than use something like Breadth-first search to find the shortest solution.

The searching looks like:
1+1
1+2
1+3
1-1
1-2
1-3
1*1
1*2
1*3
1/1
1/2
1/3
2+1
... (10 skipped)
2/3
3+1
... (10 skipped)
3/3
1+1+1
1+1+2
... (skipped a lot of lines)
3/3/3

The amount of variants:
3*4*3 = 36 for first operator,
3*4*3*4*3 = 432 for two operators,
3*4*3*4*3*4*3 = 5184 for three operators, etc.

[Eglaios]

Edited, I sure should have been more precise... Sorry...

[Eglaios]

One way to understand it is similar to a TV contest where contestants need to get as close as possible to a given number, by using only a set of numbers and using the four classic arithmetic operators on them

Uuuh actually you're pretty close...
I'm playing on a minecraft server (shame on me ), and each player has custom stats, which can be increased /decreased by spending stats scrolls...
However, the plugin is coded like crap so if one's strenght is at 99% and it uses a +15% strenght scroll, the strenght will then be at 114% because pro devs forgot about cap flooring...
I also happen to have a dupe exploit on that server so I can get as many copies of my different scrolls as I want...

Shame on me for asking something for cheating on a minecraft server on Love forum, but... that was kinda interesting overall, so...

[pgimeno]

There are many results if you search for "subset sum with repetition"; the problem is that you also want to include negative numbers and that makes the number of solutions infinite in most cases, and makes any search algorithm have a huge field to explore. With the regular subset sum with repetitions, which applies to positive numbers, you reduce the search space quickly as you find solutions; however, if negatives are possible, even with two numbers there's infinite solutions with positive factors if they are relatively prime. For example, this diophantine equation:

6*x - 11*y = N

has infinite solutions for every N. For N=0, {x=11, y=6} is one, but there are many others; for N=1, e.g. {x=2, y=1}; for N=2, {x=4, y=2} and so on. Basically, there's one solution for every x for which y = (6*x-N)/11 is a positive integer, that is, for which (6*x-N) is divisible by 11 and positive. Since 6 and 11 are relatively prime, there are infinite; there's always one x between 1 and 66 that generates an integer y, for example, and if y is negative you can increase x by 66 until it isn't. For positive numbers, however, the factors often need to be negative to satisfy the equation and that's not allowed, making the number of solutions finite (zero in many cases).

In summary, when allowing negatives, the search space is so huge that I don't dare trying to write a program that explores it.