题解 | #购物单#

转载思路来源：

https://www.bilibili.com/video/BV1SF411t7U6?from=search&seid=15688468237014115069&spm_id_from=333.337.0.0

直接上代码

import sys


inputs = []
for line in sys.stdin:
    a = line.split()
    a = [int(x) for x in a]
    inputs.append(a)

def func(inputs):
    all_money = inputs[0][0]  # 总资金
    all_store = inputs[1:]    # 总商品列表
    
    def get_fjs(zj):
        """输入主件编号，获取主件的附件编号"""
        
        fjs = [i for i, x in enumerate(all_store) if x[-1] == zj + 1]
        
        return fjs

    # 所有主件编号
    zjs = [i for i in range(len(all_store)) if all_store[i][-1] == 0]
    
    # 定义动态规划状态表
    """
    题中说价格都是 10 的整数倍，则除以10降低空间复杂度
    最外层索引 i 表示钱；
    dp[i][1] 表示购买的物件；
    dp[i][0] 表以价格i 购买 dp[i][1] 所能获得的满意度, 也是用当前的钱能买到的最大满意度。
    """
    dp = [[0, []] for _ in range(0, all_money // 10 + 1) ]
    
    for zj in zjs:
        fjs = get_fjs(zj)
        
        for money in range(all_money // 10, 0, -1):
            # 买主件
            surplus = money - all_store[zj][0] // 10
            if surplus >= 0:
                myd = all_store[zj][0] * all_store[zj][1] + dp[surplus][0]
                if myd > dp[money][0]:
                    dp[money][0] = myd
                    dp[money][1].append(zj)
            if fjs != []:
                "题干中提到每个商品的附件不超过2个"
                # 买一个附件的情况
                for fj in fjs:
                    sub_surplus = surplus - all_store[fj][0] // 10
                    if sub_surplus >= 0:
                        myd = (all_store[zj][0] * all_store[zj][1] 
                               + all_store[fj][0] * all_store[fj][1] 
                               + dp[sub_surplus][0])
                        if myd > dp[money][0]:
                            dp[money][0] = myd
                            dp[money][1] = []
                            dp[money][1].extend(dp[sub_surplus][1])
                            dp[money][1].append(zj)
                            dp[money][1].append(fj)
                # 买两个附件的情况
                if len(fjs) == 2:
                    sub_surplus = surplus - all_store[fjs[0]][0] // 10 - all_store[fjs[1]][0] // 10
                    if sub_surplus >= 0:
                        myd = (all_store[zj][0] * all_store[zj][1] 
                               + all_store[fjs[0]][0] * all_store[fjs[0]][1] 
                               + all_store[fjs[1]][0] * all_store[fjs[1]][1] 
                               + dp[sub_surplus][0])
                        if myd > dp[money][0]:
                            dp[money][1] = []
                            dp[money][0] = myd
                            dp[money][1].extend(dp[sub_surplus][1])
                            dp[money][1].append(zj)
                            dp[money][1].extend(fjs)
                    
    print(max([x[0] for x in dp]))



if __name__ == '__main__':
    func(inputs)