a greedy bag algorithm

greedy_bag.lua

--[[ 
我有一个小书包呀咿呀咿呀呦，贪心算法求次优解 
由调用者保证nNum的合法性（nNum >= 0 and nNum <= #tbNumSet） 
]] 
function FindCloseSet(nTarget, nNum, tbNumSet) 
	local tbResult = {} 
	local nSum = 0 
	local nLocal = 1 
	for i = 1, nNum do 
		nSumnSum = nSum + tbNumSet[i] 
		table.insert(tbResult, tbNumSet[i]) 
		nLocal = i 
	end 
	local nDistance = math.abs(nTarget - nSum) 
	for j = nLocal + 1, #tbNumSet do 
		local nNewSum = 0 
		local nRepLocal = 0 
		for k = 1, #tbResult do 
			local nLocalSum = nSum - tbResult[k] + tbNumSet[j] 
			local nLocalDis = math.abs(nTarget - nLocalSum) 
			if nLocalDis < nDistance then 
				nNewSum = nLocalSum 
				nRepLocal = k 
				nDistance = nLocalDis 
			end 
		end 
		if nRepLocal ~= 0 then 
			table.remove(tbResult, nRepLocal) 
			table.insert(tbResult, tbNumSet[j]) 
			nSum = nNewSum 
		end 
	end 
	return tbResult 
end 
 
local nTarget = 58 
local nNum = 2 
local tbNumSet = { 1, 4, 8, 11, 10, 80, 110, -5, -8, -100 } 
n = 100 
t = { 86, 23, 19, 8, 42, 12, 49 } 
table.sort(t) 
local tbResult = FindCloseSet(n, 4, t) 
print(unpack(tbResult))