前言
【算法趣题】是来自图灵程序设计丛书绝云译的《程序员的算法趣题》，书中是用Ruby实现的。这里是用python来实现。
问题描述
书中的例子是以安置在公交上的零钱兑换机为背景，详细可看P019。这里，我换一种场景来描述。
假如我在天猫某个店铺里抽到了一张1000元的店铺红包，该红包只能购买4种商品，这四种商品的价格分别为10元、50元、100元、500元，每种商品可以购买多件，但一张订单最多只能购买15件商品，超过15件就要自掏邮费，且一个红包仅一张订单使用。为了不浪费这1000元的红包，也不想出邮费，请问购买的商品有多少种组合？
思路
这个题的解法和【算法趣题】Q02 数列的四则运算类似，只要把满足条件的组合一一列举出来就可以了。
根据条件，1000元最多能买500元的商品2件，最多能买100元的商品10件，最多能买50元的商品15件，最多能买10元的商品15件。
假设能购买500元、100元、50元、10元商品的件数分别为price500、price100、price50、price10，
则 price500+price100+price50+price10 应小于等于 15，
且
500*price500 + 100*price100 + 50*price50 + 10*price10 应等于 1000
python3实现
循环法
count = 0
for price500 in range(3): # 500元商品最多2件
for price100 in range(11): # 100元商品最多10件
for price50 in range(16): # 50元商品最多15件
for price10 in range(16): # 10元商品最多15件
if price500+price100+price50+price10 <= 15 and 500*price500 + 100*price100 + 50*price50 + 10*price10 == 1000:
count = count + 1
comb = [500]*price500+[100]*price100+[50]*price50 +[10]*price10
print('兑换方式' + str(count) + ': ' + str(comb))
print('兑换方式共有：' + str(count) + '种。')
更灵活方式
上述解法非常直观，但可扩展性比较差，比如只有100元红包，只能购买3种商品，价格分别为10元、20元、50元，一张订单最多5件商品，问有多少种购买组合？
这样的话，上述代码改动就比较大了。接下去，我们就用比较灵活的方式来实现。
def combi(price_set, limit, total_price):
from functools import reduce
import itertools
count = 0
for i in range(2,limit+1):
for comb in itertools.combinations_with_replacement(price_set, i):
if reduce(lambda x, y: x+y, comb) == total_price:
count = count + 1
print('兑换方式' + str(count) + ': ' + str(comb))
print('兑换方式共有：' + str(count) + '种。')
price_set 是各种商品的价格列表，limit是件数的限制，total_price是红包价值。
这里要注意一下，python3中，reduce()函数已经从全局名字空间里移除了，如果要用的话，必须引入其所在的模块fucntools。
如果把条件更换一下，只要修改对应的参数即可：
补充
关于组合，可以看下itertools模块，但模块提供的函数都是处理迭代功能的，返回值不是list，而是迭代对象，只有用for循环迭代的时候才真正计算。
来说一下我的思路，为什么会想到用 itertools.combinations_with_replacement()函数。
首先，四种商品的价格列表 price_set = [10, 50, 100, 500]，每种价格的商品最多可以取15件，那我就把最多可能的都列出来，price_set * 15，也就是形成一个新的列表，新列表里有15个10，15个50，15个100和15个500 共60个。相当于我在这60件商品里任选2~15件，满足这任选的2~15件商品的总价是1000.
如此算法大概是：
初始化组合数 = 0
for i in range(2,16): # 遍历2~15件
任选其中i件
if （这i件商品的总和==1000）:
记下这个组合
原组合数+1任选其中的几件，是不是想到了数学中的组合？而itertools 库提供了四个可用于生成数据排列和组合的迭代器。
1. combinations(可迭代对象，组合元素个数)
import itertools
for item in itertools.combinations('abcd', 2):
print(item)
从运行结果看，combinations 函数返回的组合是按顺序的，且不会将每个单独的元素自己跟自己组合。
2. combinationa_with_replacement(可迭代对象，组合元素个数)
for item in itertools.combinations_with_replacement('abcd', 2):
print(item)
从运行结果看，combinationa_with_replacement函数返回的组合与combinations相比，增加了元素自己与自己的组合。
3. product(*可迭代对象, repeat = 1)
arrays = [('a','b'),('c','d'),('e','f')]
for item in itertools.product(*arrays):
print(item)
product函数根据一系列输入的可迭代对象计算笛卡尔积。
4. permutations(可迭代对象, 组合元素个数)
for item in itertools.permutations('abcd', 2):
print(item)
从结果看，permutations函数返回的是排列，但不包括元素自己与自己的组合。
熟悉了以上4个函数，应该清楚这里选用哪个函数了。
