书包

1. --[[ 
2. 我有一个小书包呀咿呀咿呀呦，贪心算法求次优解 
3. 由调用者保证nNum的合法性（nNum >= 0 and nNum <= #tbNumSet） 
4. ]] 
5. function FindCloseSet(nTarget, nNum, tbNumSet) 
6.     local tbResult = {} 
7.     local nSum = 0 
8.     local nLocal = 1 
9.     for i = 1, nNum do 
10.         nSumnSum = nSum + tbNumSet[i] 
11.         table.insert(tbResult, tbNumSet[i]) 
12.         nLocal = i 
13.     end 
14.     local nDistance = math.abs(nTarget - nSum) 
15.     for j = nLocal + 1, #tbNumSet do 
16.         local nNewSum = 0 
17.         local nRepLocal = 0 
18.         for k = 1, #tbResult do 
19.             local nLocalSum = nSum - tbResult[k] + tbNumSet[j] 
20.             local nLocalDis = math.abs(nTarget - nLocalSum) 
21.             if nLocalDis < nDistance then 
22.                 nNewSum = nLocalSum 
23.                 nRepLocal = k 
24.                 nDistance = nLocalDis 
25.             end 
26.         end 
27.         if nRepLocal ~= 0 then 
28.             table.remove(tbResult, nRepLocal) 
29.             table.insert(tbResult, tbNumSet[j]) 
30.             nSum = nNewSum 
31.         end 
32.     end 
33.     return tbResult 
34. end 
35.  
36. local nTarget = 58 
37. local nNum = 2 
38. local tbNumSet = { 1, 4, 8, 11, 10, 80, 110, -5, -8, -100 } 
39. n = 100 
40. t = {86, 23, 19, 8, 42, 12, 49} 
41. table.sort(t) 
42. local tbResult = FindCloseSet(n, 4, t) 
43. print(unpack(tbResult)) 

转载于:

书包

1. --[[ 
2. 我有一个小书包呀咿呀咿呀呦，贪心算法求次优解 
3. 由调用者保证nNum的合法性（nNum >= 0 and nNum <= #tbNumSet） 
4. ]] 
5. function FindCloseSet(nTarget, nNum, tbNumSet) 
6.     local tbResult = {} 
7.     local nSum = 0 
8.     local nLocal = 1 
9.     for i = 1, nNum do 
10.         nSumnSum = nSum + tbNumSet[i] 
11.         table.insert(tbResult, tbNumSet[i]) 
12.         nLocal = i 
13.     end 
14.     local nDistance = math.abs(nTarget - nSum) 
15.     for j = nLocal + 1, #tbNumSet do 
16.         local nNewSum = 0 
17.         local nRepLocal = 0 
18.         for k = 1, #tbResult do 
19.             local nLocalSum = nSum - tbResult[k] + tbNumSet[j] 
20.             local nLocalDis = math.abs(nTarget - nLocalSum) 
21.             if nLocalDis < nDistance then 
22.                 nNewSum = nLocalSum 
23.                 nRepLocal = k 
24.                 nDistance = nLocalDis 
25.             end 
26.         end 
27.         if nRepLocal ~= 0 then 
28.             table.remove(tbResult, nRepLocal) 
29.             table.insert(tbResult, tbNumSet[j]) 
30.             nSum = nNewSum 
31.         end 
32.     end 
33.     return tbResult 
34. end 
35.  
36. local nTarget = 58 
37. local nNum = 2 
38. local tbNumSet = { 1, 4, 8, 11, 10, 80, 110, -5, -8, -100 } 
39. n = 100 
40. t = {86, 23, 19, 8, 42, 12, 49} 
41. table.sort(t) 
42. local tbResult = FindCloseSet(n, 4, t) 
43. print(unpack(tbResult)) 

转载于: