Posted on by Kalkicode
Code Greedy

Coin change using greedy algorithm in ruby

Ruby program for Coin change using greedy algorithm. Here problem description and other solutions.

#    Ruby program
#    Greedy algorithm to find minimum number of coins
class Change 
	#  Find minimum coins whose sum make a given value
	def minNoOfCoins(coins, n, value) 
		if (value <= 0) 
			return
		end
		#  Sort the given coins
		coins = coins.sort
		#  Use to collect coins
		record = []
		#  Auxiliary variables
		sum = 0
		i = n - 1
		c = 0
		#   Find the change coins by given value
		while (i >= 0 && sum < value) 
			#  Get coin
			c = coins[i]
			while (c + sum <= value) 
				#  Add coin
				record.push(c)
				#  Update sum
				sum += c
			end

			#  Reduce position of element
			i -= 1
		end

		print("\n Given value is ", value, "\n")
		if (sum == value) 
			v = 0
			#  When change are possible.  
			#  Display resultant coins.
			while (v < record.length) 
				print("  ", record[v])
				v += 1
			end
		else
			print(" Full change are not possible\n")
		end

	end

end

def main() 
	task = Change.new()
	coins = [6, 3, 1, 4]
	n = coins.length
	#  Value = 23
	task.minNoOfCoins(coins, n, 23)
	#  Value = 38
	task.minNoOfCoins(coins, n, 38)
	#  Value = 7
	task.minNoOfCoins(coins, n, 7)
end

main()

Output

 Given value is 23
  6  6  6  4  1
 Given value is 38
  6  6  6  6  6  6  1  1
 Given value is 7
  6  1

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment