蓝桥杯促销购物（python）

题目见：蓝桥杯促销购物

思路：这是一个典型的背包问题，采用动态规划算法。因为dp数组的维数不确定，所以通过一维dp数组表示多维的dp数组，将多维的下标输入cvindex转换成一维数组下标。

s = int(input())
promotions = list()

# n对c, k,最后p
for i in range(s):
    promotions.append([int(x) for x in input().split()])


b = int(input())
goal = list()
# c编号，k数量，p原价,goalgoods是商品编号集合
for i in range(b):
    goal .append([int(x) for x in input().split()])
goalgoods = set([x[0] for x in goal])


# 去掉包含不需要商品的促销方式
noneed = list()
for i in range(s):
    for j in range(promotions[i][0]):
        if promotions[i][j*2+1] not in goalgoods:
            noneed.append(i)
for x in range(len(noneed)-1, -1, -1):
    promotions.pop(noneed[x])
    

Maxnum = 25

# dp数组初始化,下标为0的都为0
total = 1
for i in goal:
    total *= i[1]+1
dp = [0 for i in range(total)]


def cvindex(indexes):
    global goal
    res = 0
    accumulate = 1
    for i in range(len(indexes)):
        res += indexes[i]*accumulate
        accumulate *= goal[i][1]+1
    return res

# 迭代dp数组,下标current达到时停止,用一个字典存货物名与下标的关系
goodstoindex = dict(zip([x[0] for x in goal], [i for i in range(b)]))

current = [0 for i in range(b)]
final = [x[1] for x in goal]


# 计算使用这种优惠的最终价格，在current和promotion顺序相同的假定下
def cal(promotion, current):
    global goal, goalgoods, goodstoindex
    for i in range(promotion[0]):
        curin = goodstoindex[promotion[i*2+1]]
        current[curin]-=promotion[(i+1)*2]
        if current[curin] < 0:
            return float("inf")
    return dp[cvindex(current)]+promotion[-1]


# 更新dp表顺序！很重要， i表示第i个商品种类
# 前i-1个下标确定了，更新第i及之后所有商品
def update(indexes, i):
    global dp
    if i < b:
        for j in range(goal[i][1]+1):
            if j != 0:
                best = dp[cvindex(indexes)] + goal[i][2]
                indexes[i]+=1
                # 尝试每一种优惠
                for  x in promotions:
                    temp = cal(x, indexes[:])
                    if temp