回复“每周一测” - Make change

class Array; def sum; inject( nil ) { |sum,x| sum ? sum+x : x }; end; end
def clonearray(arr)
	b = []
	for a in arr
	  b << a 
	end
	return b
end
def match(condidatesolution,avail,paymoney)
	@temp = 0
	for i in 0..avail.size-1
		@temp += condidatesolution[i] * avail[i]
	end
	return ( @temp ==paymoney)
end
def printarray(arr)
	print "["
	for a in arr
		print a.to_s + ","
	end
	print "]"
end
def makechange2(paymoney,avail)
	# 相当于解方程 aW+bX+cY+dZ = paymoney
	# 要求：
	# 这里W,X,Y,Z = 10,7,5,1
	# 要求找到所有的[a,b,c,d]的集合中
	#  a+b+c+d 是最小的作为解。
	#
	# 最大范围的数组 [3,5,7,39]
	
	# 获得最大数组 coinmax
	@coinmax = []
	@coincurr = []
	for coinavail in avail
	  @coinmax << paymoney/coinavail
	  @coincurr << 0
	end
	#printarray @coinmax
	#printarray @coincurr
	@size = @coincurr.size()
	# 循环遍历可能解空间，升位，直到 @coincurr[@size-1] > @coinmax[@size-1] 
	@i =0 
	@mincoincount = 99999 

	while @coincurr[@size-1] <= @coinmax[@size-1] 
	    if match(@coincurr,avail,paymoney)
		  print "a solution:"
		  printarray @coincurr
		  puts
		  @coincount = 	@coincurr.sum
		  if @coincount < @mincoincount 
		    @mincoincount = @coincount
		    @finalsolution = clonearray(@coincurr)		    
		  end 
		end	
		@first = @coincurr.shift
		@coincurr.insert(0,@first+1)
		#print "--"
		#printarray @coincurr
		for i in 0..(@size -2)
		  if @coincurr[i] > @coinmax[i] 
		    @coincurr[i+1] = @coincurr[i+1] + @coincurr[i] / (@coinmax[i]+1)
		    @coincurr[i] = @coincurr[i] % (@coinmax[i]+1)
		  end
		end  
	end
	print "finalsolution:"
	printarray @finalsolution
end
makechange2( 39,[10,7,5,1])