题解 | #购物单#

购物单

http://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4

转载思路来源:

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)
全部评论

相关推荐

小叮当411:应该是1-3个月吧
点赞 评论 收藏
分享
哈哈哈哈哈哈哈哈哈哈这个世界太美好了
凉风落木楚山秋:毕业出路老师不管,你盖个章他好交差就完事了,等你盖完毕业了就不关他事情了
点赞 评论 收藏
分享
门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
zhch7:建议9✌️把学历加黑加粗,如果实在offer可能是觉得佬不会去
投了多少份简历才上岸
点赞 评论 收藏
分享
评论
1
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务