CareerCup 8.7

Given an infinite number of quarters(25 cents), dimes(10 cents), nickels(5 cents) and pennies(1 cent), write code to calculate the number of ways representing n cents.

把所有硬币放在一块，比如vector里，然后用一个recursion找出所有的子集。给所有子集求和？

whatever 发表于 2012-7-31 22:55
把所有硬币放在一块，比如vector里，然后用一个recursion找出所有的子集。给所有子集求和？

一种硬币取了多个是怎么放进vector里的？

BinaryWitch 发表于 2012-7-31 23:13
一种硬币取了多个是怎么放进vector里的？

我意思是，比如有3个quarters,2个 dimes, 4个nickels，就弄一个container里面放{25,25,25,10,10,5,5,5,5} 然后取子集

def coin(n):
    out= [(a,b,c,d)
            for a in range(1+int(n/25))
            for b in range(1+int((n-25*a)/10))
            for c in range(1+int((n-25*a-10*b)/5))
            for d in range(1+n-25*a-10*b-5*c)
            if 25*a+10*b+5*c+d==n]
    print 'for sum=%d, there are %d solutions' %(n, len(out))
    return len(out)
  

whatever 发表于 2012-7-31 23:20
我意思是，比如有3个quarters,2个 dimes, 4个nickels，就弄一个container里面放{25,25,25,10,10,5,5,5,5} ...

每种都有无限个 如果把从 1 ~ n/value 都放进集合 再找 时空都不好

BinaryWitch 发表于 2012-7-31 23:49
每种都有无限个 如果把从 1 ~ n/value 都放进集合 再找 时空都不好

看错了。。。看成finite了。。囧

finite解法也一样啊。。。无非就是每种面值硬币的数目都是0 ~ min of {remaining sum/面值, 硬币总数}

小K 发表于 2012-7-31 23:31
def coin(n):
    out= [(a,b,c,d)
            for a in range(1+int(n/25))

这个够简洁的 哈哈 不知道有没有了解完全背包 有兴趣可以看看
就这个题 常数个物品来说 时间可到 O(n) 滚动数组优化空间到 O(n)
       public static int __8_7(int n) {
                int[] values = {1, 5, 10, 25};
                int[] f = new int[n+1];
                f[0] = 1;
                for (int v: values) {
                        for (int i = v; i <= n; ++i) {
                                f += f[i-v];
                        }
                }
                return f[n];
        }

参考了一下solution
https://github.com/parker0203/careercup/blob/master/8_7.c