How do I find out what group of numbers fit into a number

[StungDev (Stung)]

Hello, I am making a recommended trade feature that shows the player witch pets you can put in to make it a fair trade

Lets say I have a table of pet values {1, 5, 8, 2, 9} and one number (the other players total) 20
what is the best way I can get witch numbers out of the table I need to use to get close to 20?

[DioGotHeaven (LowQualityDio)]

I didn’t really get it but here’s an idea (math time)
9 + 8 = 17
17 + 2 = 19
19 + 1 = 20

[azqjanna]

You are trying to solve whats called the Knapsack problem - Wikipedia
There are lots of ways to do this and many of them are approximations, because an exact solution is usually hard. Look at the Variations section and see if any of those apply to you, sometimes a variation on the problem is easier to solve.

[StungDev (Stung)]

This was exactly what I needed thanks!
My code:

function Knapsack(Number, Denominations)
	local Required = {}
	local Total = 0
	
	table.sort(Denominations, function(a,b)
		return a > b
	end)
	for _=1,#Denominations do
		for i, Denomination in ipairs(Denominations) do
			if Total + Denomination <= Number then
				table.insert(Required, Denomination)
				table.remove(Denominations, i)
				Total += Denomination
				break
			end
		end
	end
	
	return Required
end

print(Knapsack(20, {1,3,7,6,8,1,3}))

It returns {8, 7, 3, 1, 1} witch is 20