动态规划之01背包问题及其优化(python实现)「建议收藏」

动态规划之01背包问题及其优化(python实现)「建议收藏」动态规划之01背包问题及其优化(python实现)**背包问题(**Knapsackproblem)是一种组合优化的NP完全问题。问题描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。解决思路:动态规划,对每一件物品遍历背包容量,当背包可容纳值大于等于当前物品,与之前已放…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

动态规划之01背包问题及其优化(python实现)

**背包问题(**Knapsack problem)是一种组合优化的NP完全问题。
问题描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。

解决思路:动态规划,对每一件物品遍历背包容量,当背包可容纳值大于等于当前物品,与之前已放进去的物品所得价值进行对比,考虑是否需要置换。

递归定义如下:
这里写图片描述

python实现算法如下:

def bag(n, c, w, v):
    """ 测试数据: n = 6 物品的数量, c = 10 书包能承受的重量, w = [2, 2, 3, 1, 5, 2] 每个物品的重量, v = [2, 3, 1, 5, 4, 3] 每个物品的价值 """
    # 置零,表示初始状态
    value = [[0 for j in range(c + 1)] for i in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, c + 1):
            value[i][j] = value[i - 1][j]
            # 背包总容量够放当前物体,遍历前一个状态考虑是否置换
            if j >= w[i - 1] and value[i][j] < value[i - 1][j - w[i - 1]] + v[i - 1]:
                value[i][j] = value[i - 1][j - w[i - 1]] + v[i - 1]
    for x in value:
        print(x)
    return value

输入测试数据结果如下:最大价值为15
这里写图片描述

接下来,输出背包里所放的物品,只需从尾遍历物品,当value大于上一行同样位置的value时,表示放进该物品

代码如下:

def show(n, c, w, value):
    print('最大价值为:', value[n][c])
    x = [False for i in range(n)]
    j = c
    for i in range(n, 0, -1):
        if value[i][j] > value[i - 1][j]:
            x[i - 1] = True
            j -= w[i - 1]
    print('背包中所装物品为:')
    for i in range(n):
        if x[i]:
            print('第', i+1, '个,', end='')

输出结果:
这里写图片描述

以上时间复杂度为O(cn),已经不能再优化了。但空间复杂度O(cn)可以优化为O(c)。
思路:尾部迭代,每个状态表示上一次的最佳结果。
实现代码如下;

def bag1(n, c, w, v):
    values = [0 for i in range(c+1)]
    for i in range(1, n + 1):
        for j in range(c, 0, -1):
            # 背包总容量够放当前物体,遍历前一个状态考虑是否置换,这里的value[j]即为上一次最佳结果
            if j >= w[i-1]:
                values[j] = max(values[j-w[i-1]]+v[i-1], values[j])
    return values

完整代码:

#coding:utf-8

def bag(n, c, w, v):
    """ 测试数据: n = 6 物品的数量, c = 10 书包能承受的重量, w = [2, 2, 3, 1, 5, 2] 每个物品的重量, v = [2, 3, 1, 5, 4, 3] 每个物品的价值 """
    # 置零,表示初始状态
    value = [[0 for j in range(c + 1)] for i in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, c + 1):
            value[i][j] = value[i - 1][j]
            # 背包总容量够放当前物体,遍历前一个状态考虑是否置换
            if j >= w[i - 1] and value[i][j] < value[i - 1][j - w[i - 1]] + v[i - 1]:
                value[i][j] = value[i - 1][j - w[i - 1]] + v[i - 1]
    for x in value:
        print(x)
    return value

def show(n, c, w, value):
    print('最大价值为:', value[n][c])
    x = [False for i in range(n)]
    j = c
    for i in range(n, 0, -1):
        if value[i][j] > value[i - 1][j]:
            x[i - 1] = True
            j -= w[i - 1]
    print('背包中所装物品为:')
    for i in range(n):
        if x[i]:
            print('第', i+1, '个,', end='')

def bag1(n, c, w, v):
    values = [0 for i in range(c+1)]
    for i in range(1, n + 1):
        for j in range(c, 0, -1):
            # 背包总容量够放当前物体,遍历前一个状态考虑是否置换
            if j >= w[i-1]:
                values[j] = max(values[j-w[i-1]]+v[i-1], values[j])
    return values


if __name__ == '__main__':
    n = 6
    c = 10
    w = [2, 2, 3, 1, 5, 2]
    v = [2, 3, 1, 5, 4, 3]
    value = bag(n, c, w, v)
    # [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    # [0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2]
    # [0, 0, 3, 3, 5, 5, 5, 5, 5, 5, 5]
    # [0, 0, 3, 3, 5, 5, 5, 6, 6, 6, 6]
    # [0, 5, 5, 8, 8, 10, 10, 10, 11, 11, 11]
    # [0, 5, 5, 8, 8, 10, 10, 10, 12, 12, 14]
    # [0, 5, 5, 8, 8, 11, 11, 13, 13, 13, 15]
    show(n, c, w, value)
    # 最大价值为: 15
    # 背包中所装物品为:
    # 第 2 个,第 4 个,第 5 个,第 6 个,
    print('\n空间复杂度优化为N(c)结果:', bag1(n, c, w, v))
    #空间复杂度优化为N(c)结果: [0, 5, 5, 8, 8, 11, 11, 13, 13, 13, 15]

如有错误,欢迎指正和交流~

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/164409.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 请说明 Iaas Paas 和 Saas 分别提供的服务和特点_一张图看懂系列

    请说明 Iaas Paas 和 Saas 分别提供的服务和特点_一张图看懂系列编译:老夫子原文:https://www.bmc.com/blogs/saas-vs-paas-vs-iaas-whats-the-difference-and-how-to-choose/从小型企业到全球企业,云都是一个非常热门的话题,它是一个非常广泛的概念,涵盖了很多在线领域。无论是应用程序还是基础架构部署,当您开始考虑将业务转移到云时,了解各种云服务的差异和优势比以往任何时候…

    2022年10月22日
  • DEDECMS点击主栏目默认显示第一个子栏目列表的方法

    DEDECMS点击主栏目默认显示第一个子栏目列表的方法

  • 如何用burpsuite抓包[通俗易懂]

    如何用burpsuite抓包[通俗易懂]首先:使用火狐浏览器,并下载插件proxy点击上图右边的按钮并选择附加组件查询并下载插件配置代理点击options,然后add需要抓包时点击绿色的就行了burpsuite首先我们来到proxy界面在开启插件代理和interceptison的情况下点击某个链接即可抓取数据包需要改包发包的话可以直接在这里修改后直接forward或者同时按ctrl和r在下图…

  • openssl-heartbleed漏洞学习

    openssl-heartbleed漏洞学习了解漏洞Heartbleed漏洞:Heartbleed漏洞是openssl的一个漏洞,这个严重漏洞(CVE-2014-0160)的产生是由于未能在memcpy()调用受害用户输入内容作为长度参数之前正确进行边界检查。攻击者可以追踪OpenSSL所分配的64KB缓存、将超出必要范围的字节信息复制到缓存当中再返回缓存内容,这样一来受害者的内存内容就会以每次64KB的速度进行泄露。背景和影响:…

  • 关于 HikariPool-1 – Starting… 启动问题

    关于 HikariPool-1 – Starting… 启动问题问题今天开了一台新的阿里云服务器,启动Docker容器内的Springboot程序,数据库(阿里云的)一直死活连不上去。2020-12-0114:39:56.178INFO[svc-activity,,,]8—[main]com.zaxxer.hikari.HikariDataSource:HikariPool-1-Starting…2020-12-0114:49:57.493ERROR[svc-activity,,,]8-

  • C++中list用法详解[通俗易懂]

    C++中list用法详解[通俗易懂]1.关于list容器list是一种序列式容器。list容器完成的功能实际上和数据结构中的双向链表是极其相似的,list中的数据元素是通过链表指针串连成逻辑意义上的线性表,也就是list也具有链表的主要优点,即:在链表的任一位置进行元素的插入、删除操作都是快速的。list的实现大概是这样的:list的每个节点有三个域:前驱元素指针域、数据域和后继元素指针域。前驱元素指针域保存了前驱元素的首地

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号