问题描述

最小费用购物：
商店中每种商品都有标价。例如，一朵花的价格是2元，一个花瓶的价格是5元。为了吸引客户，商店提供了一组优惠价格商品。优惠价格是把一种或者多种商品分成一组，并且降价销售。例如：三朵花的价格不是6元而是5元。2个花瓶加一朵花的优惠价格是10元。是设计一种算法，计算出某一顾客所购商品应付的最小费用。

题目分析

首先我们考虑这样的问题，当我们通过一种优惠方案以后，那么会产生一个新的子问题，而且产生同样的状态可能不止一条路经，但是这个状态的最小值只有一个，那么这个题目是满足无后效性，又有大量重叠子问题，还符合最优化原理，那么我们选择动态规划来做这道题目是十分合适的。

算法思想实现

通过遍历整张dp表, 我们可以从（0, 0, 0, 0, 0）到（a,b,c,d,e）一直遍历，我们分别以此此判断整个表的每个状态的最小值，当满足某种优惠条件时候，我们把当前状态减去一个优惠方案，会得到一个之前已经算过的重复状态，我们可以通过查表法轻松的得到这个答案，如果满足多个优惠方案，那么我们需要把这几个方案返回的最小值计算出来，填入表中。如果不满足，直接返回单价×数量。这样经过一次遍历以后，我们就可以完整的得到这个dp表，并且实现了备忘录功能，消除了大量重叠子问题。

代码设计思路

我们可以通过一个多维数组来实现这个dp表，每次遍历表中的每个数据，分支进行判断所有优惠方案，并且返回每个分支的值，再这些值当中取得一个最小值放入表中。
数据设计以及测试用例：
2 //代表用户购买两种商品
7 8 2 //七号商品，买8个，单价两元
8 11 5 //八号商品，买11个，单价五元

2 //两种优惠方案
1 7 3 5 //优惠方案涉及1种商品，编号为7,需要3个,优惠价格为5元
2 7 1 8 2 10 // 优惠方案涉及2种商品，编号为7,需要1个。编号为8,需要两个。优惠价格为10元

最后得到整个最小优惠价格：价格的期望值为60。

算法图解

代码展示

def MinCost():
    # 创建一个dp五维数组表,用来做成备忘录 dp[6][6][6][6][6]
    dp = []
    for a in range(10):
        dp.append([])
        for b in range(10):
            dp[a].append([])
            for c in range(10):
                dp[a][b].append([])
                for d in range(10):
                    dp[a][b][c].append([])
                    for e in range(10):
                        dp[a][b][c][d].append(0)

    # 定义一个商品列表 goods[5][3]
    goods = []
    for a in range(5):
        goods.append([])
        for b in range(3):
           goods[a].append(0) 

    # 定义一个优惠商品列表 special_offer[99][12]
    special_offer = []
    for a in range(99):
        special_offer.append([])
        for b in range(12):
            special_offer[a].append(0)

    # 定义由m种类优惠方案
    m_num = 2

    # 定义用户购买了几种商品
    n_num = 2

    # 定义两个数组便于计算
    I = [0,0,0,0,0]

    # 定义一个最小值
    min_price = 1000000

    # 初始化goods表
    n_num = int(input("请输入需要买几种商品:"))
    for i in range(n_num):
        name = int(input("请输入商品序列号："))
        amount = int(input("请输入商品数量："))
        price = int(input("请输入商品序单价："))
        goods[i][0] = name
        goods[i][1] = amount
        goods[i][2] = price


    m_num = int(input("请输入有几种优惠方案:"))
    for i in range(m_num):
        number = int(input("请输入第{0}种方案涉及几种商品:".format(i+1)))
        special_offer[i][0] = number
        for j in range(number):
            special_offer[i][j*2+1] = int(input("请输入设计到的第{0}种商品的编号:".format(j+1)))
            special_offer[i][j*2+2] = int(input("请输入{0}种商品的需要的数量:".format(j+1)))
        special_offer[i][number*2+1] = int(input("请输入该方案的优惠价格:"))

    # 遍历所有商品
    # 第一种商品
    for I[0] in range(goods[0][1]+1):
        for I[1] in range(goods[1][1]+1):
            for I[2] in range(goods[2][1]+1):
                for I[3] in range(goods[3][1]+1):
                    for I[4] in range(goods[4][1]+1):
                        # 遍历所有的优惠条件是否满足
                        min_price = I[0]*goods[0][2] + I[1]*goods[1][2]+I[2]*goods[2][2]+I[3]*goods[3][2]+I[4]*goods[4][2]
                        for i in range(m_num):
                            index = [I[0], I[1], I[2], I[3], I[4]]
                            Num = special_offer[i][0]
                            for tmp in range(Num):
                                # 加一个判断，如果序列号可以对上 special_offer[i][j*2+1]
                                for j in range(5):
                                    if goods[j][0] == special_offer[i][tmp*2+1]:
                                        index[j] = I[j] - special_offer[i][tmp*2+2]
                                        break

                            cost = []
                            if index[0]>=0 and index[1]>=0 and index[2]>=0 and index[3]>=0 and index[4]>=0:
                                # 符合优惠条件
                                cost.append(dp[index[0]][index[1]][index[2]][index[3]][index[4]]+special_offer[i][Num*2+1])
                            ret = sorted(cost)
                            for y in cost:
                                if y!=0:
                                    min_price = y
                        dp[I[0]][I[1]][I[2]][I[3]][I[4]] = min_price 
    return dp[I[0]][I[1]][I[2]][I[3]][I[4]]
    
def main():
    a = MinCost() 
    print(a)
if __name__ == "__main__":
    main()