论坛首页 → Ruby版 → ruby →

Ruby每周一测 - 找零钱

 
浏览 8109 次
主题：Ruby每周一测 - 找零钱
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
  • kiol
  • 等级: 初级会员
  • 用户头像
  • 文章: 5
  • 积分: 10
时间：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
  • 等级: 三钻会员
  • 用户头像
  • 性别:
  • 文章: 1077
  • 积分: 1485
  • 来自: 上海
时间：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 请登录后投票
  • Quake Wang
  • 等级: 三钻会员
  • 用户头像
  • 性别:
  • 文章: 387
  • 积分: 1476
  • 来自: 上海
时间：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 请登录后投票
  • 庄表伟
  • 等级: 资深会员资深会员
  • 用户头像
  • 性别:
  • 文章: 1666
  • 积分: 3471
  • 来自: 上海
时间：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 请登录后投票
  • Quake Wang
  • 等级: 三钻会员
  • 用户头像
  • 性别:
  • 文章: 387
  • 积分: 1476
  • 来自: 上海
时间：2008-03-29
引用
是一个意思，不过原文提供的解法优化了一下，把能够整除的小值硬币移除掉，不参与计算： 
inject([]) {|mem, var| mem.any? {|c| c%var == 0} ? mem : mem+[var]}
返回顶楼
   
0 请登录后投票
  • hongkong
  • 等级: 初级会员
  • 用户头像
  • 性别:
  • 文章: 4
  • 积分: 10
  • 来自: 南京
时间：2008-03-30
引用
不知有没有哪个测试驱动高手，能小步骤用测试驱动方法寻出方案
期待啊
返回顶楼
   
0 请登录后投票
  • lllyq
  • 等级: 一钻会员
  • 用户头像
  • 性别:
  • 文章: 289
  • 积分: 972
  • 来自: 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
  • 等级: 初级会员
  • 用户头像
  • 文章: 5
  • 积分: 10
时间：2008-03-31
引用
第二个算法好像是按步走的，就是每一次都用所有的硬币情况试一遍，并记录累积。
直到第一次累积到a，这就是所用步骤最少也就是硬币最少的解法。
但是我怀疑他的效率。
返回顶楼
   
0 请登录后投票
  • javasweet
  • 等级: 初级会员
  • 用户头像
  • 性别:
  • 文章: 1
  • 积分: 0
  • 来自: 北京
时间：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 请登录后投票
 
论坛首页 → Ruby版 → ruby

跳转论坛:
JavaEye推荐
    快速回复 引用上一条消息 (Alt+S)