Ruby每周一测 - 找零钱

Java版,对11个测试分别循环1000次,总共需要15ms.

public class Test {

	public static int[] change(int change, int[] coins) {

		// 初始化 硬币种类
		if (coins == null) {
			int[] cs = { 25, 10, 5, 1 };
			coins = cs;
		}

		// 硬币种类的个数
		int count = coins.length - 1;

		// 优化 忽略用不到的大面额硬币
		int start = 0;
		for (; start <= count; start++) {
			if (change >= coins[start]) {
				break;
			}
		}
		if (start != 0) {
			count -= start;
			int[] cs = new int[count + 1];
			System.arraycopy(coins, start, cs, 0, count + 1);
			coins = cs;
		}

		// 得到结果
		int[] ns = change(change, coins, count);

		// 将用不到的大面额的硬币的个数设置为0
		if (start != 0) {
			count += start;
			int[] cs = new int[count + 1];
			System.arraycopy(ns, 0, cs, start, ns.length);
			ns = cs;
		}
		return ns;
	}

	public static int[] change(int change, int[] coins, int count) {

		// 最少的硬币个数据
		int min = change / coins[0];
		if (min * coins[0] == change) {
			int[] ns = new int[count + 1];
			ns[0] = min;
			return ns;
		} else {
			min++;
		}
		// 最多的硬币个数据
		int max = change / coins[count] + 1;

		for (int current = min; current <= max; current++) {
			int[] r = new int[count + 1];

			// 初始值
			r[0] = current;

			do {
				// 进位
				if (r[0] == 0) {
					int i = 1;
					for (; i < count; i++) {
						if (r[i] != 0) {
							break;
						}
					}
					r[i + 1]++;
					r[i - 1] = r[i] - 1;
					r[i] = 0;
				} else {
					r[0]--;
					r[1]++;
				}
				// 比较
				int sum = 0;
				for (int i = 0; i <= count; i++) {
					sum += r[i] * coins[i];
				}
				if (sum == change) {
					return r;
				}

			} while (r[count] != current); // 循环结束

		}
		return null;
	}

	public static void main(String[] args) {

		long start = System.currentTimeMillis();
		for (int i = 0; i < 1000; i++) {
			eq(change(25, new int[] { 25 }), new int[] { 1 });
			eq(change(10, new int[] { 10 }), new int[] { 1 });
			eq(change(1, new int[] { 1 }), new int[] { 1 });
			eq(change(5, new int[] { 3, 2 }), new int[] { 1, 1 });
			eq(change(5, new int[] { 4, 3, 2 }), new int[] { 0, 1, 1 });
			eq(change(39, new int[] { 25, 10 }), null);
			eq(change(14, new int[] { 10, 7, 1 }), new int[] { 0, 2, 0 });
			eq(change(14, new int[] { 5, 3, 2 }), new int[] { 1, 3, 0 });
			eq(change(12, new int[] { 22, 3, 2 }), new int[] { 0, 4, 0 });
			eq(change(40, new int[] { 20, 19, 1 }), new int[] { 2, 0, 0 });

			eq(change(427, new int[] { 10000, 1000, 10, 1 }), new int[] { 0, 0,
					42, 7 });
		}
		long end = System.currentTimeMillis();
		System.out.println((end - start) + "ms");
	}

	public static boolean eq(int[] a, int[] b) {
		boolean r;
		if (a == null) {
			r = b == null;
		} else {
			r = true;
			int m = a.length - 1;
			for (int i = 0; i <= m; i++) {
				if (a[i] != b[i]) {
					r = false;
				}
			}
		}
		return r;
	}

}

def make_change(amount, coins=[25, 10, 5, 1])
begin
  plan = []
  for am in coins.min..amount do
    if coins.include?(am) then
      plan[am] = [am]
    else
      size = 999999
      for a in coins.min..am/2 do
        if plan[a] and plan[am-a] then
          s = plan[a].length + plan[am-a].length
          if s < size then
            size = s
            plan[am] = plan[a] + plan[am-a]
          end
        end
      end
    end
  end
  plan[amount]
rescue StandardError => bang
  nil
end
end

这个方法和QuakeWang翻译的第二种方法类似。其实动态规划一般不考虑用递归。递归用到桟，桟一般较小，当递归层次很深的时候有可能桟溢出。第二种方法是递推，简单来说，就是从最基本的情况出发。例如这里，递归函数是

M(k) = min{M(1)+M(k-1), M(2)+M(k-2), ..., M(k/2, n-k/2)}

递归的方法是从 k = amount 的情况开始考虑。而递推的方法是从 k = 1 开始考虑。所以递推是先计算 k = 1 时，M(k) = ?，然后 k = 2 时，M(k) = ?，一直到 k = amount，M(k) = ?。

递推法因为没有用桟，而是用堆作为储存空间，所以递推法一般较递归要好。递推法也更好理解。

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])