动态规划/递归 | HJ16 购物单

# 最优解1：动态规划
n, m = map(int,input().split())
primary, annex = {}, {}
for i in range(1,m+1):
    x, y, z = map(int, input().split())
    if z==0:#主件
        primary[i] = [x, y]
    else:#附件
        if z in annex:#第二个附件
            annex[z].append([x, y])
        else:#第一个附件
            annex[z] = [[x,y]]
m = len(primary)#主件个数转化为物品个数
dp = [[0]*(n+1) for _ in range(m+1)]
w, v= [[]], [[]]
for key in primary:
    w_temp, v_temp = [], []
    w_temp.append(primary[key][0])#1、主件
    v_temp.append(primary[key][0]*primary[key][1])
    if key in annex:#存在主件
        w_temp.append(w_temp[0]+annex[key][0][0])#2、主件+附件1
        v_temp.append(v_temp[0]+annex[key][0][0]*annex[key][0][1])
        if len(annex[key])>1:#存在两主件
            w_temp.append(w_temp[0]+annex[key][1][0])#3、主件+附件2
            v_temp.append(v_temp[0]+annex[key][1][0]*annex[key][1][1])
            w_temp.append(w_temp[0]+annex[key][0][0]+annex[key][1][0])#3、主件+附件1+附件2
            v_temp.append(v_temp[0]+annex[key][0][0]*annex[key][0][1]+annex[key][1][0]*annex[key][1][1])
    w.append(w_temp)
    v.append(v_temp)
for i in range(1,m+1):
    for j in range(10,n+1,10):#物品的价格是10的整数倍
        max_i = dp[i-1][j]
        for k in range(len(w[i])):
            if j-w[i][k]>=0:
                max_i = max(max_i, dp[i-1][j-w[i][k]]+v[i][k])
        dp[i][j] = max_i
print(dp[m][n])

# 最优解2：递归
def solve(i, j):
    """
    i表示遍历到第i件物品，j表示剩余钱数
    """
    if i == n+1:
        return 0
    if dp[i][j] != 0:
        return dp[i][j]
    if v[i - 1] > j or a[i - 1] != 0:
        dp[i][j] = solve(i + 1, j)
    if j >= v[i - 1] and a[i - 1] == 0:  # 买得起索引为i-1的物品
        lst = []
        for inx in range(n):
            if a[inx] == i:
                lst.append(inx)
        if len(lst) == 0:  # 没有附件
            dp[i][j] = max(solve(i+1, j), solve(i+1, j-v[i - 1])+s[i-1])
        elif len(lst) == 1:  # 有1个附件
            dp[i][j] = max(solve(i+1, j), solve(i+1, j-v[i - 1])+s[i-1])
            if v[i-1]+v[lst[0]] <= j:
                dp[i][j] = max(dp[i][j], solve(i+1,j-v[i-1]-v[lst[0]])+s[i-1]+s[lst[0]])
        elif len(lst) == 2:  # 有2个附件
            dp[i][j] = max(solve(i+1, j), solve(i+1, j-v[i - 1])+s[i-1])
            i1, i2 = lst
            if v[i-1]+v[i1] <= j:  # 可以买主件+附件1
                dp[i][j] = max(solve(i+1, j), solve(i+1, j-v[i - 1])+s[i-1], 
                               solve(i+1, j-v[i-1]-v[i1])+s[i-1]+s[i1])
            if v[i-1]+v[i2] <= j:  # 可以买主件+附件2
                dp[i][j] = max(solve(i+1, j), solve(i+1, j-v[i - 1])+s[i-1], 
                               solve(i+1, j-v[i-1]-v[i2])+s[i-1]+s[i2])
            if v[i-1]+v[i1]+v[i2] <= j:  # 可以买主件+附件1+附件2
                dp[i][j] = max(solve(i+1, j), solve(i+1, j-v[i - 1])+s[i-1], 
                               solve(i+1, j-v[i-1]-v[i1])+s[i-1]+s[i1],
                               solve(i+1, j-v[i-1]-v[i2])+s[i-1]+s[i2],
                               solve(i+1, j-v[i-1]-v[i1]-v[i2])+s[i-1]+s[i1]+s[i2])
    return dp[i][j]

while True:
    try:
        m, n = list(map(int, input().split(" ")))
        v, s, a = [], [], []
        m //= 10
        for i in range(n):
            value, pri, attach = list(map(int, input().split()))
            v.append(value // 10)
            s.append(pri*value)
            a.append(attach)
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        res = solve(1, m)
        print(res)
    except:
        break

# 我的代码：参考动态规划最优解
class Good:
    def __init__(self, id, price, weight, belong) -> None:
        self.id = id  # 商品编号
        self.price = price  # 商品价格
        self.weight = weight  # 商品满意度：价格*重要度
        self.belong = belong
        self.attach = []  # 商品附件

    def add_attach(self, good):
        self.attach.append(good)

while True:
    try:
        m, N = list(map(int, input().split(" ")))
        # 1、dp数组长度为总钱数，将商品价格与总钱数同比缩小10倍，缩小dp长度
        # 2、dp由2维减为1维度，实际只记录：遍历原2维数组时当前行的上一行
        m //= 10
        dp = [0 for _ in range(m + 1)]  # 总钱数为0,1,2...m
        goods = [None, ]
        for i in range(1, N + 1):
            p, w, b = list(map(int, input().split(" ")))
            good = Good(i, p // 10, w * p, b)  # 题目说商品价格为10的整数倍
            goods.append(good)
        for good in goods[1:]:  # 遍历商品，将所有附件添加到对应主件的attach中
            if good.belong != 0:
                goods[good.belong].add_attach(good)
        for good in goods[1:]:
            if good.belong == 0:  # 遍历主件
                for j in reversed(range(m + 1)):
                    if j >= good.price:
                        dp[j] = max(dp[j], dp[j - good.price] + good.weight)
                        # 根据主件拥有附件的个数，判断怎么买让满意度最大
                        if len(good.attach) == 0:
                            continue
                        elif len(good.attach) == 1:
                            attach1 = good.attach[0]
                            # 不买;主;主+附1
                            if j >= good.price + attach1.price:  
                                dp[j] = max(
                                    dp[j],
                                    dp[j-good.price-attach1.price] + good.weight + attach1.weight,
                                )
                        elif len(good.attach) == 2:
                            attach1 = good.attach[0]
                            attach2 = good.attach[1]
                            # 不买;主;主+附1;主+附2;主+附1+附2
                            if (j >= good.price + attach1.price):  
                                dp[j] = max(
                                    dp[j],
                                    dp[j-good.price-attach1.price] + good.weight + attach1.weight,
                                )
                            if (j >= good.price + attach2.price):  
                                dp[j] = max(
                                    dp[j],
                                    dp[j-good.price-attach2.price] + good.weight + attach2.weight,
                                )
                            if (j >= good.price + attach1.price + attach2.price):  
                                dp[j] = max(
                                    dp[j],
                                    dp[j-good.price-attach1.price-attach2.price] + good.weight + \
                                        attach1.weight + attach2.weight,
                                )
                    else:
                        break
        print(dp[m])
    except:
        break

用时：7h