论坛首页 → 编程语言技术论坛 →

Ruby每周一测 - 找零钱

浏览 26606 次
锁定老帖子 主题：Ruby每周一测 - 找零钱
精华帖 (4) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
  • kiol
  • 等级: 初级会员
  • 文章: 54
  • 积分: 90
  • 来自: ...
   发表时间：2008-03-28  
有个bug，改了一下。 
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
    tail = counter.delete_at(idx)
    counter.concat(make_change(tail, valid_coins)) if tail > 0
      
    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

arr = make_change(380,[30, 20, 5, 1])
puts arr
tmp = 0
arr.each{|i| tmp += i}
puts tmp

返回顶楼
          回帖地址
0 请登录后投票
  • hax
  • 等级: 四钻会员
  • 性别:
  • 文章: 1543
  • 积分: 1795
  • 来自: 上海
   发表时间：2008-03-29  
我前面写的那个代码有bug。改后的：

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, 0, Number.POSITIVE_INFINITY));
}

// convert Map<int, int> to List<int>
// {1:2,2:0,3:1} => [1,1,3]
function mapToArray(map) {
	if (map == null) return [];
	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, offset, max) {
	var x = coins.cache[amount];
	if (x != null) return x.length <= max ? x : null;
	
	var best = null;
	
	for (var i = offset; i < coins.length; i++) {
		var c = coins[i];
		if (c * max < amount) break;
		var m = amount % c;
		if (m == 0) {
			var n = amount / c;
			max = n - 1;
			best = {length:n}; best[c] = n;
		} else if (m == amount) {
			continue;
		} else {
			var n = (amount - m) / c;
			while (n > 0) {
				var x = _makeChange1(m, coins, i + 1, max - n);
				if (x != null) {
					x[c] = x[c] ? x[c] + n : n;
					x.length += n;
					max = x.length - 1;
					best = x;
				}
				n--; m += c;
			}
		}
	}
	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, [10001, 1001, 101]);
var t2 = new Date().getTime();

out(test.length + ':[' + test + '] use time:' + (t2 - t1));

function out(s) {
	if (typeof alert != 'undefined') alert(s);
	if (typeof WScript != 'undefined') WScript.Echo(s);
}


执行结果：
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.

3926:[10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,1000
1,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,
10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10001,10
001,1001,1001,1001,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,101,1
01,101,101,101,101,101,101,101,101,101,101,101,101,101,101] use time:4375
返回顶楼
          回帖地址
0 请登录后投票
  • QuakeWang
  • 等级: 五钻会员
  • 性别:
  • 文章: 854
  • 积分: 2516
  • 来自: 上海
   发表时间：2008-03-29  
让我们来看一个简单解法： 
def make_change(amount, coins = [25,10,5,1])
  coins.map{|coin| f = amount/coin; amount %= coin; Array.new(f){coin} }.flatten
end

这里采用贪心算法，每次总是用最大的硬币去整除，然后将余下的钱用下一个硬币进行同样运算。这种算法在美元硬币体系以及其他很多国家（如人民币)下就是最优解法了(如何证明？)，但是在前面第2个例子make_change(14, [10, 7, 1])，就得不到最优解。

复杂的部分开始了：如果要得到最优解法，就要列出所有的可能组合，但是考虑到穷举法的效率问题，我们需要用更"聪明"的算法检查各种组合。这个问题实际上和计算机科学中著名的背包问题(Knapsack Problem)是等价的，用于解决这个问题常见的算法是动态规划(Dynamic programming algorithm)。

动态规划通常有2种方式:
1. 自顶向下 (Top-down)，将问题分解为多个小问题，然后用递归和备忘录(memoization)的方式进行计算，避免相同的小问题重复计算，下面这个解答就是采用这个方式： 
class Array
  def sum
    inject {|total, i| total + i}
  end
end

def make_change(amount, coins = [25, 10, 5, 1])
  # memoize solutions
  optimal_change = Hash.new do |hash, key|
    hash[key] = if key < coins.min
      []
    elsif coins.include?(key)
      [key]
    else
      coins.
        # prune unhelpful coins
      reject { |coin| coin > key }.

        # prune coins that are factors of larger coins
      inject([]) {|mem, var| mem.any? {|c| c%var == 0} ? mem : mem+[var]}.

        # recurse
      map { |coin| [coin] + hash[key - coin] }.

        # prune unhelpful solutions
      reject { |change| change.sum != key }.

        # pick the smallest, empty if none
      min { |a, b| a.size <=> b.size } || []
    end
  end

  optimal_change[amount]
end


这里比较有意思的是利用了Ruby Hash构建器，给Hash传递了一个hash/key的block，这样传递同样的Key就不会重复计算了，配合递归就得到了结果： 
      map { |coin| [coin] + hash[key - coin] }


2. 自底向上 (Bottom-up) (这种方式我不是很明白，有谁可以解释一下？) 
def make_change(a, list = [25, 10, 5, 1])
  return nil if a < 0
  return nil if a != a.floor

  parents = Array.new(a + 1)
  parents[0] = 0
  worklist = [[0, 0]]
  while parents[a].nil? && !worklist.empty? do
    base, starting_index = worklist.shift
    starting_index.upto(list.size - 1) do |index|
      coin = list[index]
      tot = base + coin
      if tot <= a && parents[tot].nil?
        parents[tot] = base
        worklist << [tot, index]
      end
    end
  end

  return nil if parents[a].nil?
  result = []
  while a > 0 do
    parent = parents[a]
    result << a - parent
    a = parent
  end
  result.sort!.reverse!
end


-----备注分割线-----
以上是简单的翻译原文解答说明，从这个每周一测可以学到Ruby Array多种方法(map, reject, inject, min ...)，Hash构建器的妙用，以及动态规划算法入门。
可惜我不是学计算机科学的，算法是我的弱项，大家对于这2个解法的详细说明有兴趣的话，还是看原文吧： http://rubyquiz.com/quiz154.html
后续的每周一测我会挑选那些更有趣，或者能够体现Ruby语言妙用的题目，尽量少偏向算法的题目。
返回顶楼
          回帖地址
1 请登录后投票
  • 庄表伟
  • 等级: 资深会员资深会员
  • 性别:
  • 文章: 2351
  • 积分: 3481
  • 来自: 上海
   发表时间：2008-03-29   
def make_change(amount, coins = [25, 10, 5, 1],list={})
  return list[amount] if list.include?(amount)
  return [amount] if coins.include?(amount)
  first_coins=coins.select {|x| x <= amount}
  min_one_coin=nil
  min_coins=Array.new(amount)
  first_coins.each do |one_coin|
    other_coins=make_change(amount-one_coin,coins.select {|x| x <= one_coin},list)
    if other_coins && min_coins.size>other_coins.size
      min_one_coin=one_coin
      min_coins=other_coins
    end
  end
  list[amount]=return_array=min_one_coin ? [min_one_coin]+min_coins : nil
end

p make_change(14,[10,7,1],{})
p make_change(380,[20,19,1],{})
p make_change(30,[21,10,1],{})


to:Quake Wang

我这个，是不是跟你那个解法，是一个意思？
返回顶楼
          回帖地址
0 请登录后投票
  • QuakeWang
  • 等级: 五钻会员
  • 性别:
  • 文章: 854
  • 积分: 2516
  • 来自: 上海
   发表时间：2008-03-29  
是一个意思，不过原文提供的解法优化了一下，把能够整除的小值硬币移除掉，不参与计算： 
inject([]) {|mem, var| mem.any? {|c| c%var == 0} ? mem : mem+[var]}
返回顶楼
          回帖地址
0 请登录后投票
  • hongkong
  • 等级: 初级会员
  • 性别:
  • 文章: 90
  • 积分: 30
  • 来自: 南京
   发表时间：2008-03-30  
不知有没有哪个测试驱动高手，能小步骤用测试驱动方法寻出方案
期待啊
返回顶楼
          回帖地址
0 请登录后投票
  • lllyq
  • 等级: 一钻会员
  • 性别:
  • 文章: 350
  • 积分: 1022
  • 来自: Shanghai
   发表时间：2008-03-31  
要解释还挺麻烦的，这个面对面画个图就好解释了，尽量不用术语
要找的零钱为m, 假设解为Dk, Dk-1,..., D1
先做第k次决策Dk，尝试所有的零钱C(1..i)，则Dk-1=m-Dk(Ci)，他这里的解法就是用数组保存状态，整个数组长度就是m，Dk就是下标到起点的距离（默认是0，因为就是求m），然后再从m-Dk的下标开始作为起点，如果改点已被标记，根据最优解原理，就忽略
简单的例子如找7对[3, 2, 1]，Dk决策就是3, 2, 1，此时状态就是3剩4， 2剩5，1剩6，再分别对4, 5, 6重复尝试，可以举出一个重复的例子，其中5-1=4(也就是7-2-1)，与7-3=4就表示重复了，那就忽略, 一直重复没有零钱为止，重复的次数就是零钱的最优个数，然后根据保存的状态找到最优解
返回顶楼
          回帖地址
0 请登录后投票
  • blcakcat
  • 等级: 初级会员
  • 性别:
  • 文章: 1
  • 积分: 30
  • 来自: 北京
   发表时间：2008-03-31  
我贴一个用java写的，输出结果与要求的稍有不同。使用最小公倍数求最优解。

　
public static void main(String[] args) {
        int[] coins = new int[] { 11, 10, 5, 2 };
        int[] change = make_change(127, coins);
        print(change, coins);
    }

    public static int[] make_change(int amount, int[] coins) {
        return change(amount, coins, 0);
    }

    private static int[] change(int amount, int[] coins, int start) {

        int[] result = null;

        if (coins.length == 0) {
            return null;
        }

        result = new int[coins.length];

        int balance = amount;
        int gcd = 0;
        int i = 0;

        if (start == coins.length - 1) {
            gcd = coins[start];
        } else {
            gcd = gcd(coins[start], coins[start + 1]);
        }

        balance = amount;
        if (amount >= gcd) {
            result[start] = (amount / gcd) * (gcd / coins[start]);
            balance = amount - coins[start] * result[start];
        }

        if (balance == 0) {
            return result;
        } else if (start == coins.length - 1) {
            return null;
        }

        int[] firstChange = new int[coins.length];
        int pMaxCoin = -1;
        int[] minChange = null;

        amount = balance;
        i = start;

        while (i < coins.length && amount != 0) {
            firstChange[i] = amount / coins[i];
            if (pMaxCoin == -1) {
                pMaxCoin = i;
            }
            amount = amount - firstChange[i] * coins[i];
            i++;
        }

        if (amount > 0) {
            minChange = null;
        } else {
            minChange = firstChange;
        }

        int other[] = new int[coins.length];

        for (i = 1; i <= firstChange[pMaxCoin]; i++) {
            amount = balance - (firstChange[pMaxCoin] - i) * coins[pMaxCoin];
            other = change(amount, coins, start + 1);
            if (other != null) {
                other[pMaxCoin] = (firstChange[pMaxCoin] - i) + other[pMaxCoin];
                if (sum(other) < sum(minChange)) {
                    minChange = other;
                }
            }
        }
        if (minChange == null || result == null) {
            return null;
        }
        for (i = 0; i < result.length; i++) {
            result[i] = result[i] + minChange[i];
        }
        return result;
    }

    private static int lcm(int a, int b) {

        int max = a;
        int min = b;
        int c = 0;

        if (a < b) {
            max = b;
            min = a;
        }
        c = max % min;
        if (c == 0) {
            return min;
        } else {
            return lcm(min, c);
        }
    }

    private static int gcd(int a, int b) {
        int lcm = lcm(a, b);
        return a * b / lcm;

    }

    public static void print(int[] change, int[] coins) {
        if (change == null) {
            System.out.println("can'nt change");
            return;
        }
        for (int i = 0; i < change.length; i++) {
            if (change[i] > 0) {
                System.out.println(coins[i] + "×" + change[i]);
            }
        }
    }

    private static int sum(int[] a) {
        if (a == null) {
            return Integer.MAX_VALUE;
        }
        int sum = 0;
        for (int i = 0; i < a.length; i++) {
            sum += a[i];
        }
        return sum;
    }
返回顶楼
          回帖地址
0 请登录后投票
  • kiol
  • 等级: 初级会员
  • 文章: 54
  • 积分: 90
  • 来自: ...
   发表时间：2008-03-31  
第二个算法好像是按步走的，就是每一次都用所有的硬币情况试一遍，并记录累积。
直到第一次累积到a，这就是所用步骤最少也就是硬币最少的解法。
但是我怀疑他的效率。
返回顶楼
          回帖地址
0 请登录后投票
  • javasweet
  • 等级: 初级会员
  • 性别:
  • 文章: 3
  • 积分: 30
  • 来自: 北京
   发表时间：2008-04-03  
我贴一个用java写的，输出结果与要求的稍有不同。使用最小公倍数求最优解。

　Java代码
public static void main(String[] args) {  
        int[] coins = new int[] { 11, 10, 5, 2 };  
        int[] change = make_change(127, coins);  
        print(change, coins);  
    }  
 
    public static int[] make_change(int amount, int[] coins) {  
        return change(amount, coins, 0);  
    }  
 
    private static int[] change(int amount, int[] coins, int start) {  
 
        int[] result = null;  
 
        if (coins.length == 0) {  
            return null;  
        }  
 
        result = new int[coins.length];  
 
        int balance = amount;  
        int gcd = 0;  
        int i = 0;  
 
        if (start == coins.length - 1) {  
            gcd = coins[start];  
        } else {  
            gcd = gcd(coins[start], coins[start + 1]);  
        }  
 
        balance = amount;  
        if (amount >= gcd) {  
            result[start] = (amount / gcd) * (gcd / coins[start]);  
            balance = amount - coins[start] * result[start];  
        }  
 
        if (balance == 0) {  
            return result;  
        } else if (start == coins.length - 1) {  
            return null;  
        }  
 
        int[] firstChange = new int[coins.length];  
        int pMaxCoin = -1;  
        int[] minChange = null;  
 
        amount = balance;  
        i = start;  
 
        while (i < coins.length && amount != 0) {  
            firstChange[i] = amount / coins[i];  
            if (pMaxCoin == -1) {  
                pMaxCoin = i;  
            }  
            amount = amount - firstChange[i] * coins[i];  
            i++;  
        }  
 
        if (amount > 0) {  
            minChange = null;  
        } else {  
            minChange = firstChange;  
        }  
 
        int other[] = new int[coins.length];  
 
        for (i = 1; i <= firstChange[pMaxCoin]; i++) {  
            amount = balance - (firstChange[pMaxCoin] - i) * coins[pMaxCoin];  
            other = change(amount, coins, start + 1);  
            if (other != null) {  
                other[pMaxCoin] = (firstChange[pMaxCoin] - i) + other[pMaxCoin];  
                if (sum(other) < sum(minChange)) {  
                    minChange = other;  
                }  
            }  
        }  
        if (minChange == null || result == null) {  
            return null;  
        }  
        for (i = 0; i < result.length; i++) {  
            result[i] = result[i] + minChange[i];  
        }  
        return result;  
    }  
 
    private static int lcm(int a, int b) {  
 
        int max = a;  
        int min = b;  
        int c = 0;  
 
        if (a < b) {  
            max = b;  
            min = a;  
        }  
        c = max % min;  
        if (c == 0) {  
            return min;  
        } else {  
            return lcm(min, c);  
        }  
    }  
 
    private static int gcd(int a, int b) {  
        int lcm = lcm(a, b);  
        return a * b / lcm;  
 
    }  
 
    public static void print(int[] change, int[] coins) {  
        if (change == null) {  
            System.out.println("can'nt change");  
            return;  
        }  
        for (int i = 0; i < change.length; i++) {  
            if (change[i] > 0) {  
                System.out.println(coins[i] + "×" + change[i]);  
            }  
        }  
    }  
 
    private static int sum(int[] a) {  
        if (a == null) {  
            return Integer.MAX_VALUE;  
        }  
        int sum = 0;  
        for (int i = 0; i < a.length; i++) {  
            sum += a[i];  
        }  
        return sum;  
    } 

这个有bug：
         int[] coins = new int[] { 40,34,17,12,11,10,3,2 };  
        int[] change = make_change(30, coins);  
        print(change, coins);
得出的结论是 can'nt change,但是是有结果的：[17,1][11,1][2,1]或者[10,3]
返回顶楼
          回帖地址
0 请登录后投票
论坛首页 → 编程语言技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics