Ruby每周一测 - 找零钱

这是ruby quzi阿,俺不懂ruby的说.
这公式也没啥难的巴,直接手动算几个case不就知道怎么做了么？

那你可以写java代码嘛，我来翻译成ruby code好了。

不知道怎样速度算快？
我用javascript写了一个。基本上计算没有超过100毫秒的（最后结果有上百个item时），不过如果amount很大而coins都很小，会stack overflow。。。

to: T1 and hax

其实，我觉得这个问题，未必要局限于Ruby，各种语言都可以来试试呀。

欢迎贴代码上来 

偶的笔记本没电了，等我充好电就贴上来。

这个问题的解法在算法里面的难度,大致就相当于你写Java查API的级别,连脑子都要不要动的.当然不熟算法就没办法了,谁让你平时不接触数学呢?你可以看一下算法设计方面的书，随便哪一本，必有一章叫做“动态规划”，看过之后就清楚了.

如果真有那么多时间,想要在这题目上动脑子的话.不如给出这个题目贪心法的正确性证明,这还是要费些脑子的.
另外这题,即便在C下面,数据量上万的话都要20-30ms,还要做优化.所以Ruby下面就不要想在100ms级别解决了.凡是能在这个级别以下的基本上都不是最优解,赫赫.

如果只是想知道的答案的话,
可以去这里
http://acm.nankai.edu.cn
注册个号，找1132题.
题目稍微有差异,但是思路相同.

function makeChange1(amount, coins) {
	if (coins == null) coins = [25, 10, 5, 1];
	if (coins.cache == null) coins.cache = {};
	for (var i = 0; i < coins.length; i++) {
		var c = coins[i];
		var o = coins.cache[c] = {length:1};
		o[c] = 1;
	}
	return mapToArray(_makeChange1(amount, coins, Number.POSITIVE_INFINITY));
}

// convert Map<int, int> to List<int>
// {1:2,2:0,3:1} => [1,1,3]
function mapToArray(map) {
	var a = [];
	for (var k in map) {
		k = parseInt(k, 10);
		if (isNaN(k)) continue;
		var v = map[k];
		for (var i = 0; i < v; i++) a.push(k);
	}
	return a.sort(compare);
}

function compare(a, b) {
	return b - a;
}

function _makeChange1(amount, coins, max) {
	var x = coins.cache[amount];
	if (x) return x.length < max ? x : null;
	
	var best = null;
	
	for (var i = 0; i < coins.length; i++) {
		var c = coins[i];
		if (c * max < amount) break;
		var m = amount % c;
		if (m == 0) {
			n = amount / c;
			max = n - 1;
			best = {length:n}; best[c] = n;
		} else if (m == amount) {
			continue;
		} else {
			var x = _makeChange1(amount - c, coins, max - 1);
			if (x == null) continue;
			max = x.length - 1;
			best = x; best[c] = best[c] ? best[c] + 1 : 1;
		}
	}
	coins.cache[amount] = best;
	return best;
}

function eq(a, b) {
	if (a === b) return true;
	if (a instanceof Array && b instanceof Array && a.length == b.length) {
		for (var i = 0, n = a.length; i < n; i++) {
			if (a[i] != b[i]) return false;
		}
		return true;
	}
	return false;
}

function assertEq(a, b) {
	if (!eq(a, b)) throw Error(a + ' != ' + b);
}

var makeChange = makeChange1;

assertEq(makeChange(25), [25]);
assertEq(makeChange(10), [10]);
assertEq(makeChange(1), [1]);
assertEq(makeChange(5, [3, 2]), [3, 2]);
assertEq(makeChange(5, [4, 3, 2]), [3, 2]);
assertEq(makeChange(39), [25, 10, 1, 1, 1, 1]);
assertEq(makeChange(14, [10, 7, 1]), [7, 7]);
assertEq(makeChange(14, [5, 3, 2]), [5, 5, 2, 2]);
assertEq(makeChange(12, [22, 3, 2]), [3, 3, 3, 3]);
assertEq(makeChange(38, [20, 19, 1]), [19, 19]);

var t1 = new Date().getTime();
var test = makeChange(31415926, [100000,1000,10,1]);
var t2 = new Date().getTime();
WScript.Echo(test.length, '[' + test + ']', ' use time:', t2 - t1);

输出结果：
D:\sjhe\js\test\change>cscript change.js
Microsoft (R) Windows Script Host Version 5.6
Copyright (C) Microsoft Corporation 1996-2001. All rights reserved.

427 [100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,10000
0,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,1
00000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,1000
00,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,
100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100
000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000
,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,10
0000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,10000
0,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,1
00000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,1000
00,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,
100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100
000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000
,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,10
0000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,10000
0,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,1
00000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,1000
00,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,
100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100
000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000
,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,10
0000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,10000
0,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,1
00000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,1000
00,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,
100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100
000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000
,100000,100000,100000,100000,100000,100000,1000,1000,1000,1000,1000,1000,1000,10
00,1000,1000,1000,1000,1000,1000,1000,10,10,10,10,10,10,10,10,10,10,10,10,10,10,
10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10
,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,1
0,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,1,1,1,
1,1,1]  use time: 16

用了16ms。

我也来贴一个

依据coins[i] = 1 + min{coins[i - d[j]]}

c语言风格，不要笑

def make_change(amount, coins = [25, 10, 5, 1])
  
  c = Array.new
  choice = Array.new
  result = Array.new
  minchoice = 0
  
  c[0] = 0
  
  for i in 1..amount
    min = 100000
    for j in 0..(coins.size() - 1)
      if coins[j] <= i and c[i - coins[j]] < min
        min = c[i - coins[j]]
        minchoice = j
      end
      c[i] = 1 + min
      choice[i] = minchoice
    end
  end

  if c[amount] == 100001
    return nil
  else
    while amount > 0
      result.push(coins[choice[amount]])
      amount = amount - coins[choice[amount]]
    end
    result
  end
  
end

#print make_change(50)
#puts make_change(1)
#puts make_change(9,[10,2,1])
#puts make_change(8,[10,4,2])
#puts make_change(19,[10,4,2,1])
#puts make_change(38, [20, 19, 1])
#puts make_change(11, [10, 1]) 

ps:怎么测试跑的速度？

我也写了一个，不知道对不对
def make_change(amount, coins = [25, 10, 5, 1])
  return nil if amount == 0
  return [amount] if coins.include? amount
  coins_count = []
  valid_coins = coins.select{|coin| coin < amount}
  valid_coins.each do |coin|
    counter = [amount]
    idx = 0
    while  counter[idx] >= coin do
      counter << counter[idx] - coin
      counter[idx] = coin
      idx = idx.next
    end
    if counter[idx] > 0
      counter << make_change(counter[idx], valid_coins)
    else
      counter.delete_at(idx)
    end
    coins_count << counter
  end
  
  min = 9999
  result = []
  coins_count.each do |counter|
    if counter.size < min
      min = counter.size
      result = counter
    end
  end
 
  return result
end

puts make_change(380,[20,19,1])