精华内容
下载资源
问答
  • 大盗潜入博物馆,面前有5件宝物,分别有重量和价值,大盜的背包仅能负重20公 斤,请问如何选择宝物,总价值最高? 物品 重量 价值 1 2 3 2 3 4 3 4 8 4 5 8 5 9 10 动态规划解法 明确问题以后,我们需要...

    问题描述

    大盗潜入博物馆,面前有5件宝物,分别有重量和价值,大盜的背包仅能负重20公
    斤,请问如何选择宝物,总价值最高?

    物品 重量 价值
    1 2 3
    2 3 4
    3 4 8
    4 5 8
    5 9 10

    动态规划解法

    明确问题以后,我们需要建立动态规划表格
    m[(i, w)]
    其中 ii 是装物品的数量 ( 0i50\le i\le 5 )
    ww 是物品的载重 ( 0w200\le w\le 20 )
    mm 则是这些物品的总价值, 也即是我们需要存入的值。
    在这里插入图片描述
    如何填写动态规划表格呢?
    1.i=0(即没有拿宝物)和w=0(最大载重为20)这两种情况下,总价值都为0
    2.用循环对每次拿宝物数量和最大载重值进行查找填表

    • 当本次i下物品的重量>当前最大载重时,m的值就等于第i-1次总重为w的价值。
    • 否则返回 装或者不装该次物品这两种情况下的最大值
      :\color {red} {算法公式如下:}
      m(i,W)={0 if i=00 if W=0m(i1,W) if wi>Wmax{m(i1,W),vi+m(i1,Wwi)} otherwise m(i, W)=\left\{\begin{array}{ll} 0 & \text { if } i=0 \\ 0 & \text { if } W=0 \\ m(i-1, W) & \text { if } w_{i}>W \\ \max \left\{m(i-1, W), v_{i}+m\left(i-1, W-w_{i}\right)\right\} & \text { otherwise } \end{array}\right.

    动态规划实现代码

    import time
    # 按标签逐个导入宝物的重量和价值
    tr = [None, {'w':2, 'v':3}, {'w':3, 'v':4}, {'w':4, 'v':8},
         {'w':5, 'v':8}, {'w':9, 'v':10}]
    # 设置最大容量
    max_weight = 20
    # 建立动态规划表格m[(i,w)]
    # i表示取得物品个数
    # w表示物品最大限制重量
    def getTreasure(tr, max_weight):
        m = {(i,w): 0 for i in range(len(tr))
            for w in range(max_weight+1)}
        # 动态规划填补表格
        for i in range(1, len(tr)):
            for w in range(1, max_weight+1):
        # 若当前第i件物品重量超出最大载重,则不装第i件物品,总价值等于第i-1次总重为w的价值(即撑爆了不加该次的价值)
        # 否则饭回 装或者不装该次物品 这两种情况下的最大值
                if tr[i]['w'] > w: 
                    m[(i, w)] = m[(i-1, w)]
                else:
                    m[(i, w)] = max(m[(i-1, w)], 
                                    m[(i-1, w-tr[i]['w'])] + tr[i]['v'])
        return m[(len(tr)-1, max_weight)]
    t1 = time.process_time()
    print(getTreasure(tr, max_weight))
    t2 = time.process_time()
    print('Process time:\t{:.6f}'.format(t2-t1))
    

    结果
    在这里插入图片描述

    该题的递归解法

    # 用元组建立递归集合,包含重量和价值
    tr = {(2,3), (3,4), (4,8), (5,8), (9,10)}
    
    max_weight = 20
    # 建立存储表格m
    m = {}
    # 初始化记忆化表格m
    # key是(宝物组合,最大重量),value是最大价值
    
    def getTreasure(tr, w):
        if tr == set() or w == 0:
            m[(tuple(tr), w)] = 0
            return 0
        elif (tuple(tr), w) in m:
            return m[(tuple(tr), w)]
        else:
            vmax = 0
            for t in tr:
                if t[0] <= w:
    # 逐个从集合中去掉某个宝物,递归调用
    # 选出所有价值中的最大值
                    v = getTreasure(tr-{t}, w-t[0]) + t[1]
                    vmax = max(v, vmax)
            m[(tuple(tr), w)] = vmax
            return vmax
    
    
    t1 = time.process_time()
    print(getTreasure(tr, max_weight))
    t2 = time.process_time()
    print('Process time:\t{:.6f}'.format(t2-t1))
    

    结果
    在这里插入图片描述

    展开全文
  • 大盗潜入博物馆,面前有5件宝物,分别有重量和价值,大盗的背包仅能负重20公斤,请问如何选择宝物,总价值最高?   item weight value 0 2 3 1 3 4 2 4 8 3 5 8 4 9 ...

     

    大盗潜入博物馆,面前有5件宝物,分别有重量和价值,大盗的背包仅能负重20公斤,请问如何选择宝物,总价值最高?
     

    item weight value
    0 2 3
    1 3 4
    2 4 8
    3 5 8
    4 9 10

    代码及解答:

    # 宝物重量及价值
    treasure = [{'w':2,'v':3},{'w':3,'v':4},{'w':4,'v':8},{'w':5,'v':8},{'w':9,'v':10}]
    # 大盗最大承重和可能拿走的宝物最多件数
    max_w, max_num = 20, len(treasure)
    # 初始化maxvalue和treasure_used,记录在当前可选宝物范围中,大盗可拿走的最大总价值及对应宝物
    mtv = [[0 for i in range(max_w+1)] for j in range(max_num+1)]
    treasure_used= [[False for p in range(max_w+1)] for q in range(max_num+1)]
    
    # 循环添加宝物至“大盗可选清单”
    for i in range(1,max_num+1):
        need_w,get_v = treasure[i-1]['w'],treasure[i-1]['v']  # 添加的宝物的重量和价值
        for j in range(1,max_w+1):
            if i==1:  # 如果清单只有一件宝物
                if j<need_w:  # 如果当前物品重量大于背包容量
                    mtv[1][j]=0
                else:  # 如果当前物品可放入背包
                    mtv[1][j]=get_v
                    treasure_used[1][j] = True
            else:
                if j<need_w:  # 如果当前物品重量大于背包容量
                    mtv[i][j]=mtv[i-1][j]  # 和这个物品不存在时一样
                else:  
                    # 如果可以放,需要进一步决策:大于上一次选择的最佳方案则更新mtv[i][j]
                    treasure_used[i][j] = mtv[i - 1][j - need_w] + get_v> mtv[i - 1][j]
                    mtv[i][j]=max(mtv[i-1][j-need_w]+ get_v ,mtv[i-1][j])
                    #  记录在mtv[i][j]时是否选择了放入第i-1件宝物
    
    print(mtv[max_num][max_w])  # 回溯打印编号
    num=max_num
    w=max_w
    s = ""
    while num > 0:
        if treasure_used[num][w]:
            s=s+str(num-1)+" "  # 减一是因为宝物序号是从零开始的
            w = w - treasure[num-1]['w']
            num = num - 1  # 处理依据 mtv[i-1][j-need_w]+ get_v
        else:
            num = num - 1  # 处理依据 mtv[i-1][j]
    print(s)
    

     

    展开全文
  • 博物馆大盗问题(背包问题) 问题描述: 大盗的背包最多只能装20kg的物品,每件物品的重量和价值如下图所示,如何组合才能使背包中物品的价值最高。 动态规划的解法:从最简单的情况开始找到可以满足条件的物品组合...

    博物馆大盗问题(背包问题)

    问题描述:

    大盗的背包最多只能装20kg的物品,每件物品的重量和价值如下图所示,如何组合才能使背包中物品的价值最高。
    在这里插入图片描述

    动态规划的解法:从最简单的情况开始找到可以满足条件的物品组合。
    假设背包中可以装入的物品编号为0~i,背包的最大容量为W,物品最大总价值为m(i,W)
    动态规划表格如下图所示:
    在这里插入图片描述
    当可以装入背包的物品编号为0时(即背包中没有物品),价值m为0,
    当背包的最大容量为0时,背包内没有物品,价值m为0。
    在这里插入图片描述
    当编号为i的物品重量大于背包容积时,那么前i个物品的最佳组合和前i-1个物品的最佳组合相同,如第2件物品的重量为3,当背包容量为2时,该物品无法装进背包中,因此
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    当背包装的下第i号物品时,存在两种情况:
    1.i号物品装进去,那么需要给当前物品预留空间,前i-1个物品可以占据的容积为W-Wi,背包内的总价值为
    在这里插入图片描述
    2. i号物品不装进去,那么前i个物品的最佳组合和前i-1个物品的最佳组合相同;
    选取第一种和第二种情况中的最大价值为当前最佳组合的价值。
    在这里插入图片描述
    总结:
    在这里插入图片描述

    #宝物的重量和价值
    tr = [None, {'w':2,'v':3}, {'w':3,'v':4},
          {'w':4,'v':8}, {'w':5,'v':8},
          {'w':9,'v':10}]
    #大盗最大承重
    max_w = 20
    
    #初始化二维表格m[(i,w)]
    #表示前i个宝物中,最大重量w的组合,所得到的最大价值
    #当i什么都不取,或w上限为0,价值均为0
    
    m = {(i,w):0 for i in range(len(tr))
         for w in range(max_w + 1)}
    
    #逐个填写这个二维表格
    for i in range(1,len(tr)):
        for w in range(1,max_w + 1):
            if tr[i]['w'] > w:
                m[(i, w)] = m[(i-1, w)]
            else:
                m[(i,w)] = max(
                    m[(i-1,w)],
                    m[(i-1,w-tr[i]['w'])] + tr[i]['v'])
    
    print(m[len(tr)-1,max_w])
    
    
    
    
    展开全文
  • # 宝物的重量和价值 tr = [None, {'w': 2, 'v': 3}, {'w': 3, 'v': 4}, {'w': 4, 'v': 8}, {'w': 5, 'v': 8}, {'w': 9, 'v': 10} ] max_w = 20 # 初始化二维表格m{(i, w)} m = {(i, w): 0 for i in range(len...
    # 宝物的重量和价值
    tr = [None, {'w': 2, 'v': 3}, {'w': 3, 'v': 4},
          {'w': 4, 'v': 8}, {'w': 5, 'v': 8},
          {'w': 9, 'v': 10}
          ]
    
    max_w = 20
    
    # 初始化二维表格m{(i, w)}
    m = {(i, w): 0 for i in range(len(tr)) for w in range(max_w + 1)}
    
    for i in range(1, len(tr)):
        for w in range(1, max_w + 1):
            if tr[i]['w'] > w:
                m[(i,w)] = m[(i - 1, w)]
            else:
                m[(i,w)] = max(m[(i-1),w], tr[i]['v'] + m[(i - 1, w - tr[i]['w'])])
    
    # 输出结果
    print(m[(len(tr)-1, max_w)])
    print(m)
    
    展开全文
  • 同时,从申遗的契机,居民生活的改善,天人合一的外部环境,动态的内部空间,独特的和原生态客家文化等方面论证了建设永定土楼生态博物馆的可行性,将生态博物馆理念运用到永定土楼的旅游开发当中,提出了生态博物馆...
  • 课程设计代码,jsp代码,浏览器博物馆完整代码基于js平台,实现数据库连接 动态网页显示,图片轮播等功能。
  • # 宝物的重量和价值 tr = [None, {'w':2, 'v':3},{'w':3, 'v':4}, {'w':4, 'v':8},{'w':5, 'v':8}, {'w':9, 'v':10}] # 大盗最大承重 max_w = 20 # 初始化二维表格m[(i,w)] # 表示前i个宝物中,最大重量w的组合...
  • 博物馆大盗问题 Python

    2020-08-04 20:03:53
    博物馆大盗问题 问题: 大盗潜入博物馆,面前有5件宝物,分别有重量w和价值v,大盗的背包仅能负重20 kg,请问如何选择宝物,总价值最高? Item Weight Value 1 2 3 2 3 4 3 4 8 4 5 8 5 9 10 思路...
  • 新起典文旅认为当前国内的博物馆沉浸式投影越来越受公众喜欢,越来越多的博物馆以虚拟现实、增强现实、全息投影、多点触控等数字化技术为基础,对文物藏品等内容进行三维建模、还原相关历史场景、开发博物馆馆藏资源...
  • 在管理者、文物和场馆这种实时动态的互动中,文物能够活得更健康更长寿。]利用信息技术代替实际操作,减少浪费,节约时间和费用,从而实现供应链的无缝对接和整合为实现物流流程信息化管理,苏州新导采用信息化管理...
  • 如何针对博物馆安防系统的实际具体需求,制订切实有效的监控防范体系是目前文物保护的主要课题。  文博单位的安防系统主要包括视频监控、防盗报警和门禁三个主项以及楼宇对讲、声音复核和保卫巡更等诸多子项。作为...
  • 等时间到六点,他们开始在博物馆里到处乱跑来找到对方(他们没法给对方打电话因为电话漫游费是很贵的) 不过,尽管他们到处乱跑,但他们还没有看完足够的艺术品,因此他们每个人采取如下的行动方法:每一分钟做...
  • 为完成对博物馆敞开后传染性疫情动态改变状况的实时监测,针对博物馆从头敞开所面对的防疫风险防控问题,首套集物联网、大数据和人工智能等技能于一体的博物馆文物定位监测数据收集体系。博物馆文...
  • 从改变传统的文物标识方式、展厅和库房管理入手,到实现文物数据实时采集、实时自动追踪、可视化动态管理、库存e-kanban、出入库领导审批、库房温湿度实时监测、以及本地和远程管理,从而在博物馆实现全面数字化智能...
  • 博物馆大盗 数据结构:每个藏品封装为一个对象,对象有属性价值和重量。 动态规划:对于每个藏品,盗贼都有两种选择:偷或不偷。通过递归,可以模拟选择过程。 优化:剪枝。在选择之前,先判断如果选择之后,重量...
  • 同时给出了该方法应用于构建博物馆个性化导览系统的应用示例。实验结果表明该方法具有较高的定位精度和推荐准确率。所提室内导览方法具有通用性好和组网成本低的特点,能够较好地满足博物馆等室内导览系统应用需求,...
  • 目录解决问题的策略一、知识概览二、博物馆大盗问题2.1 动态规划解法2.2 递归解法 解决问题的策略 一、知识概览 本章介绍了动态案例分析——博物馆大盗问题。分别用动态规划和递归法求解。最后对递归进行小结。 二...
  • 讨论:博物馆大盗问题 大盗潜入博物馆, 面前有5件宝物, 分别有重量和价值, 大盗的背包仅能负重20公斤, 请问如何选择宝物, 总价值...博物馆大盗问题:动态规划表格 递归解法 # 宝物的重量和价值 tr = {(2, 3), (3
  • 目录一、博物馆大盗问题 一、博物馆大盗问题 大盗潜入博物馆, 面前有5件宝物, 分别有重量和价值, 大盗的背包仅能负重20公斤, 请问如何选择宝物, 总价值最高? item weight value 1 2 3 2 3 4 3 4 8...
  • 0-1背包问题是经典的动态规划问题,这个问题大多用这样的故事开场:一个小偷溜进了一家博物馆博物馆里排列着N件珍稀古董,每件古董都有重量和价值,而小偷带来的背包有重量限制W。因此,小偷的目的就是要选择部分...
  • 适用于Android主屏幕的生活博物馆。 Muzei是一种动态壁纸,每天都会用著名的艺术品轻轻地刷新您的主屏幕。 它还会退入背景,使艺术品模糊和变暗,以使您的图标和小部件始终受到关注。 只需双击墙纸或打开Muzei应用...
  • 动态关联表

    2008-04-12 19:37:00
    还好,我们有很多博物馆来收藏它们。”- Microsoft 董事长 Bill Gates,Forbes.com,2004 年 10 月 4 日。Shawn MSDN Online 总编辑同样精彩的话还有:日产CEO卡洛斯.戈恩:“汽车业是一种‘骡子’的行业,而非‘赛马...
  • 博物馆大盗问题: #这个动态规划的思路与常见的貌似不同,常见的可看北航课件 # 宝物的重量与价值 第零号设为None表示从1计数 tr = [None,{'w':2,'v':3},{'w':3,'v':4},{'w':4,'v':8},{'w':5,'v':8},{'w':9,'v':...
  • (1)博物馆(BZOJ3270) 题面还是见黄学长的博客吧传送门 因为这里有环形,我们显然不能直接向傻X一样递推 我们定义id[x][y]id[x][y]表示一人在x,一人在y的状态 再标记d[x]d[x]为点xx的度 ratio[x]ratio[x]为不...
  • 例如,在医院、办公大楼、百货商店和博物馆中存在各种各样的机器人系统。此外,一些多机器人系统已经被开发用于更复杂的任务,这些任务可以由整个机器人团队来完成,而不仅仅是单个机器人。这些任务包括表面清洁、...
  • 博物馆致力于保护和庆祝计算机历史,并且是世界上最大的国际计算人工制品馆的所在地,其中包括计算机硬件,软件,文档,临时数据库,照片和动态图像。 博物馆通过大型展览,备受赞誉的演讲者系列,充满活力的...

空空如也

空空如也

1 2 3
收藏数 57
精华内容 22
关键字:

动态博物馆