当前位置: 首页 > news >正文

DP——背包问题

DP——背包问题

  • 01背包问题
  • 分数背包问题
  • 多重背包问题
  • 完全背包问题

在这里插入图片描述

当我们谈论背包问题时,可以想象成一个小朋友要去旅行,但是他只能带一个容量有限的背包。他有一些物品可以选择放入背包,每个物品都有自己的重量和价值。小朋友的目标是在不超过背包容量的情况下,选择物品使得总价值最大化。

01背包问题

01 01 01背包问题中,小朋友只能选择每个物品要么完全放入背包,要么完全不放入背包。每个物品都有自己的重量和价值,而背包有一个固定的容量限制。小朋友的目标是选择物品,使得它们的总价值最大化,同时不超过背包的容量限制。

举个例子,小朋友的背包容量是 10 10 10,他有以下物品可供选择:

物品 A A A:重量 3 3 3,价值 4 4 4
物品 B B B:重量 4 4 4,价值 5 5 5
物品 C C C:重量 2 2 2,价值 3 3 3

在这种情况下,小朋友可以选择所有物品,它们的总重量是 9 9 9,总价值是 12 12 12,同时不超过背包的容量限制。

分数背包问题

在分数背包问题中,小朋友可以选择每个物品的一部分放入背包。每个物品都有自己的重量和价值,而背包有一个固定的容量限制。小朋友的目标是选择物品的部分,使得它们的总价值最大化,同时不超过背包的容量限制。

举个例子,小朋友的背包容量是10,他有以下物品可供选择:

物品A:重量3,价值4
物品B:重量10,价值6
物品C:重量2,价值3

在这种情况下,小朋友可以选择物品 A A A的全部,物品B的一部分(重量为 5 5 5),以及物品 C C C的全部。这样总重量是 10 10 10,总价值是 4 + ( 5 / 10 ) ∗ 6 + 3 = 10 4 + (5/10)*6 + 3 = 10 4+(5/10)6+3=10,同时不超过背包的容量限制。

多重背包问题

在多重背包问题中,每个物品有自己的重量、价值和可用数量。背包有一个固定的容量限制。小朋友的目标是选择物品的数量,使得它们的总价值最大化,同时不超过背包的容量限制和物品的可用数量限制。

举个例子,小朋友的背包容量是10,他有以下物品可供选择:

物品A:重量3,价值4,可用数量2
物品B:重量4,价值5,可用数量1
物品C:重量2,价值3,可用数量3

在这种情况下,小朋友可以选择物品A两个以及物品C两个。这样总重量是(3 2) + (22) = 10,总价值是(4*2) +(3 *2) =14,同时不超过背包的容量限制和物品的可用数量限制。

完全背包问题

在无界背包问题中,每个物品有自己的重量和价值,但是每个物品的数量是无限的。背包有一个固定的容量限制。小朋友的目标是选择物品的数量,使得它们的总价值最大化,同时不超过背包的容量限制。

举个例子,小朋友的背包容量是10,他有以下物品可供选择:

物品A:重量3,价值4
物品B:重量4,价值5
物品C:重量2,价值3

在这种情况下,小朋友可以选择物品C五个。这样总重量是5* 2) = 14,总价值为3*5 = 15,同时不超过背包的容量限制。

http://www.lryc.cn/news/124654.html

相关文章:

  • 【从零学习python 】29. 「函数参数详解」——了解Python函数参数的不同用法
  • 10个经典战略分析模型,助力洞察市场明确优势
  • C++(Qt)软件调试---将调试工具安装到AeDebug(11)
  • 浅谈限流式保护器在住宅电气防火的应用
  • ChatGPT助力ModStartBlog,博客写作更智能
  • Jpa与Druid线程池及Spring Boot整合(二): spring-boot-starter-data-jpa 踏坑异常处理方案
  • Vue3组件库
  • AUTOSAR从入门到精通-【应用篇】基于 CAN/LIN 总线的智能配电监控系统的研究设计
  • 数据安全服务能力评定资格证书-申请流程
  • 用js快速生成一个简单的css原子库 例如: .mr-18 .pl-18
  • Java鹰眼轨迹服务 轻骑小程序 运动健康与社交案例
  • 【产品经理】微信小程序隐私保护指引
  • springboot创建websocket服务端
  • 网络安全攻防实战:探索互联网发展史
  • pwm接喇叭搞整点报时[keyestudio的8002模块]
  • 配置listener tcps加密 enable SSL encryption for Oracle SQL*Net
  • 【Sklearn】基于逻辑回归算法的数据分类预测(Excel可直接替换数据)
  • 自然数的拆分问题
  • du -mh命令
  • MySQL 8 group by 报错 this is incompatible with sql_mode=only_full_group_by
  • Mongodb (四十一)
  • 16 dlsys GAN
  • css3-flex布局:基础使用 / Flexbox布局
  • MYSQL-习题掌握
  • Python-迭代
  • 【论文阅读】DEPCOMM:用于攻击调查的系统审核日志的图摘要(SP-2022)
  • 大语言模型之一 Attention is all you need ---Transformer
  • 数字鸿沟,让气候脆弱者更脆弱
  • Tomcat 部署优化
  • Django框架-使用celery(一):django使用celery的通用配置,不受版本影响