背包多重约束

2024-04-26

我有一个动态规划问题,我花了几个小时研究但没有结果。

第一部分很简单:你有一背包物品,你必须最大化这些物品的价值,同时将它们保持在一定的重量以下。

问题的第二部分是相同的,只是现在也有一个项目限制。例如:

您可以放入袋子中的物品的最大价值是多少,以便在重量和物品限制的情况下价值最大化?

我不知道如何实现这个问题的第二部分,我正在寻找一个通用算法。


在动态规划中solution http://www.geeksforgeeks.org/knapsack-problem/如果没有项目限制,您将拥有 2D 矩阵,其中 Y 轴是项目索引,X 轴是重量。然后对于每个项目,您选择之间的最大重量对

  • 如果物品重量
  • 不含物品的重量值

以下是 Python 标准解决方案的示例:

def knapsack(n, weight, values, weights):
    dp = [[0] * (weight + 1) for _ in range(n + 1)]

    for y in range(1, n + 1):
        for x in range(weight + 1):
            if weights[y - 1] <= x:
                dp[y][x] = max(dp[y - 1][x],
                               dp[y - 1][x - weights[y - 1]] + values[y - 1])
            else:
                dp[y][x] = dp[y - 1][x]

    return dp[-1][-1]

现在,当您添加项目限制时,您必须选择每个项目的最大值、值、使用的项目数量三元组

  • 如果物品重量
  • 重量值和排除物品的n件物品

为了表示项目数量,您只需将第三个维度添加到之前使用的表示已使用项目数量的矩阵中即可:

def knapsack2(n, weight, count, values, weights):
    dp = [[[0] * (weight + 1) for _ in range(n + 1)] for _ in range(count + 1)]
    for z in range(1, count + 1):
        for y in range(1, n + 1):
            for x in range(weight + 1):
                if weights[y - 1] <= x:
                    dp[z][y][x] = max(dp[z][y - 1][x],
                                      dp[z - 1][y - 1][x - weights[y - 1]] + values[y - 1])
                else:
                    dp[z][y][x] = dp[z][y - 1][x]

    return dp[-1][-1][-1]

简单演示:

w = 5
k = 2
values = [1, 2, 3, 2, 2]
weights = [4, 5, 1, 1, 1]
n = len(values)

no_limit_fmt = 'Max value for weight limit {}, no item limit: {}'
limit_fmt = 'Max value for weight limit {}, item limit {}: {}'

print(no_limit_fmt.format(w, knapsack(n, w, values, weights)))
print(limit_fmt.format(w, k, knapsack2(n, w, k, values, weights)))

Output:

Max value for weight limit 5, no item limit: 7
Max value for weight limit 5, item limit 2: 5

请注意,您可以在内存消耗方面对示例进行一些优化,因为将第 z 项添加到解决方案时,您只需要知道 z - 1 项的解决方案。此外,您还可以检查是否可以将 z 件物品放入重量限制以下,如果不能,则相应地减少物品限制。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

背包多重约束 的相关文章

  • 使用主方法求解 T(n) = 2T(n/2) + n/log n 和 T(n) = 4T(n/2) + n/log n 之间的差异

    我最近偶然发现了一个资源 其中 2T n 2 n log ntypeMM 宣布复发无法解决 我接受它作为一个引理 直到今天 另一种资源被证明是矛盾的 在某种意义上 根据资源 下面的链接 其中的 Q7 和 Q18 是建议 分别在问题中的1和2
  • 删除队列中的最后一个元素

    我需要删除队列的最后一个元素 我唯一可以使用的操作是 Peek 获取第一个元素而不删除它 Enqueue element 向队列末尾插入一个元素 Dequeue 删除第一个元素 IsEmpty true 或 false 队列是否为空 而且我
  • 如何将无向图转换为 DAG?

    The 维基页面 http en wikipedia org wiki Directed acyclic graph Relation to other kinds of graphs says 任何无向图都可以通过为其顶点选择总顺序并将每
  • 高维最近邻搜索的最佳数据结构

    我实际上正在处理高维数据 50 000 100 000 个特征 并且必须对其执行最近邻搜索 我知道随着维度的增长 KD 树的性能很差 而且我还了解到 一般来说 所有空间分区数据结构都倾向于对高维数据执行详尽的搜索 此外 还有两个重要事实需要
  • 固定大小集以包含给定集的最大数量

    我有大约 1000 组尺寸 1 4 1 3 3 5 6 4 5 6 7 5 25 42 67 100 是否有可能找到包含最大数量的给定集合的大小为 20 的集合 检查每一个100 80 20 集 效率低下 我不太确定这是 NP 完全的 考虑
  • 如何确定算法函数的复杂度?

    您如何知道算法函数对于特定操作是否需要线性 常数 对数时间 它取决于CPU周期吗 您可以通过三种方式 至少 做到这一点 在网上查找算法 看看它是如何描述其时间复杂度的 根据输入大小 自己检查算法 查看嵌套循环和递归条件等内容 以及每个循环运
  • 在 C# 中实现动态代理的最佳方法是什么?

    我需要在 C 中创建动态代理 我希望这个类包装另一个类 并采用它的公共接口 转发对这些函数的调用 class MyRootClass public virtual void Foo Console Out WriteLine Foo int
  • 如何将一组重叠范围划分为不重叠范围?

    假设您有一组范围 0 100 一 0 75 b 95 150 c 120 130 d 显然 这些范围在某些点上重叠 您将如何剖析这些范围以生成不重叠范围的列表 同时保留与其原始范围相关的信息 在本例中为范围后面的字母 例如 运行算法后的上述
  • 寻找将集合映射到整数的双射函数

    对于任意两个序列 a b 其中 a a1 a2 an 且 b b1 b2 bn 0a b具有相同的元素 而不关心它们的顺序 例如 如果 a 1 1 2 3 b 2 1 3 1 c 3 2 1 3 则 f a f b f a f b 我知道有
  • 在 C++ 中通过引用传递 std 算法谓词

    我正在尝试从 a 中删除元素std list并保留已删除元素的一些统计信息 为此 我使用列表中的remove if 函数 并且我有一个谓词 我想使用这个谓词来收集统计数据 这是谓词的代码 class TestPredicate privat
  • 分而治之策略来确定列表中是否有超过 1/3 的相同元素

    我正在使用分治算法来确定列表中是否有超过 1 3 的元素相同 例如 1 2 3 4 不 所有元素都是唯一的 1 1 2 4 5 是的 其中 2 个是相同的 没有排序 是否有分而治之的策略 我陷入了如何划分的困境 def is valid i
  • URL路径相似度/字符串相似度算法

    我的问题是我需要比较 URL 路径并推断它们是否相似 下面我提供了要处理的示例数据 GROUP 1 robots txt GROUP 2 bot html GROUP 3 phpMyAdmin 2 5 6 rc1 scripts setup
  • 快速约会算法

    我在一家咨询公司工作 大部分时间都在客户所在地 正因为如此 我很少见到同事 为了更好地了解彼此 我们将安排一个晚宴 会有很多小桌子 方便人们聊天 为了在聚会期间与尽可能多的不同的人交谈 每个人都必须每隔一段时间 比如每小时 换一张桌子 如何
  • 如何有效地找到距给定点最远的点(从一组点中)?

    我正在寻找一种算法或数据结构来解决以下问题 给你一组点 S 然后你会得到另一个点形式的 Q 查询 对于每个查询 找到集合中距离给定点最远的点 集合中最多有 10 5 个点和 10 5 个查询 所有点的坐标都在 0 到 10 5 范围内 我想
  • 直接选择排序与交换选择排序

    有什么区别直接选择排序 vs 交换选择排序 今天我陷入了一场争论 我的教授在他的讲义中使用了这两个术语 维基百科和任何教科书或网站都会为您提供的选择排序就是他所说的 交换选择排序 我以前从未听说过 交换选择排序 这个术语 仅 选择排序 并且
  • 从一种数字系统转换为另一种数字系统后会有多少位数字

    主要问题 有多少位数字 让我解释 我有一个二进制数 11000000 十进制数是192 转换为十进制后 它有多少位 以十进制表示 在我的示例中 它是 3 位数字 但是 这不是问题 我在互联网上搜索并找到了一种用于整数部分的算法和一种用于小数
  • 在 O(n) 时间内排序?

    我被这个问题困扰了 2周 知道如何处理它吗 令 L 为 n 个不同整数的列表 假设 L 的 x 的元素在 1 750 范围内 设计线性排序算法对 L 的元素进行排序 我已经尝试过插入排序 但我不确定我的方法是否正确 Construct an
  • 用于开始和/或包含搜索的最快字符串集合结构/算法是什么

    我有以下情况 我有一个大的字符串集合 比如说 250 000 平均长度可能是 30 我要做的就是在这些搜索中进行许多搜索 大多数搜索都是 StartsWith 和 Contains 类型的 该集合在运行时是静态的 这意味着选择的集合的初始读
  • 在java中使用BUBBLE SORT对二维字符串数组进行排序

    类似的问题已经被问过 但从来没有关于二维字符串数组 因此在尝试了很长时间之后我找不到我想要的 我正在尝试使用 BubbleSort 对 java 中的 2D 字符串数组进行排序 作为输入 我收到一个二维字符串数组 一个表 以及您应该排序的
  • 解开 Knuth 的结:如何重构意大利面条式代码?

    这个问题的灵感来自如何将流程图转化为实施 https stackoverflow com questions 36647765它询问如何通过算法消除goto代码中的语句 这answer https stackoverflow com a 3

随机推荐

  • Aurelia 中的多个触发器

    我想在 aurelia 中触发两种不同的方法 实现此目的的最佳方法是什么 a 我可能会做以下事情 HTML a JavaScript yourFunction event parts this toggleSize size parts t
  • 在触发器上传递 JSON 数据

    我正在调用返回 JSON 数据的服务 Script ajax type POST url some service dataType json success function response if response status ok
  • MongoDB 推文数据库的日期范围查询失败

    我正在尝试对 mongo 数据库中的推文集合执行范围查询 由于某种原因 以下查询将起作用 db posts find created at gte Fri Nov 25 00 00 00 0000 2011 lt Fri Nov 25 23
  • 从节点子进程检索值

    var fp ffprobe fileName show streams grep var width exec fp width function err stdout stderr return stdout alert stdout
  • NgbDropdown autoClose“外部”不起作用

    我正在使用 Angular4 和 ng bootstrap 我想在下拉菜单外部单击时关闭下拉菜单 文档的其余部分 查看文档后我发现autoClose 类型 boolean 外面 里面 但是当我尝试将其设置为参数 config autoClo
  • 是否可以在浏览器中使用 javascript 对用户系统进行基准测试

    随着 Html5 开始普及 我们看到更多关于视频或画布元素等的实验 当使用画布进行实验时 例如用粒子制作烟花 1000 个粒子可能在现代机器上运行良好 但在 3 年机器上可能会运行得很慢 无论如何 是否可以对用户系统进行基准测试以动态更改画
  • 当摘要具有嵌入文本输入并且用户按空格键时,如何防止 html 详细信息元素切换

    我在处于打开状态的详细信息元素的摘要标签内有一个文本输入 目的是捕获用户输入 该输入最终将显示为详细信息元素 见下文 但是 当用户在输入文本时按空格键时 详细信息元素会切换 我想阻止这种情况 我预计这可以在按键事件中使用 stopPropa
  • xgboost中的eval_metric和feval有什么区别?

    有什么区别feval and eval metric在xgb train中 这两个参数仅用于评估目的 Kaggle 的帖子提供了一些见解 https www kaggle com c prudential life insurance as
  • Java、类路径、类加载 => 同一 jar/项目的多个版本

    我知道对于经验丰富的程序员来说这可能是一个愚蠢的问题 但我有一个库 一个 http 客户端 我的项目中使用的一些其他框架 jar 需要它 但它们都需要不同的主要版本 例如 httpclient v1 jar gt Required by c
  • 迭代器后继者

    我想用另一个迭代器 同类 的后继者初始化一个迭代器 任意类型 以下代码适用于随机访问迭代器 但不适用于前向或双向迭代器 Iterator i j 1 一个简单的解决方法是 Iterator i j i 但这不起作用初始化语句for 循环的
  • 如何通过分页从附加页面中提取数据

    我成功返回了第一页数据 并获得了 API 调用中存在的附加数据页数 这是我尝试提取附加数据页的代码 try const response UrlFetchApp fetch root endpoint params const respon
  • 如何从右向左对齐日期选择器?

    datepicker dob on click function datepicker datepicker format dd mm yyyy autoclose true
  • 设计评论表

    基本上我想创建一个评论系统 其中评论可能有也是评论的父母 但我也希望他们可能有可能是其他东西的父母 例如用户或产品 即 我希望能够对产品发表评论 用户 其他评论或几乎任何资源 我该怎么做呢 当前表 标签 产品 用户 评论 编辑 这将适用于流
  • jQuery 获取容器的 html,包括容器本身

    我如何获取 container 上的 html 包括 container 而不仅仅是其中的内容 div div test 1 div div test 2 div div test 3 div div test 4 div div 我有这个
  • 多个 Docker 容器和 Celery

    我们现在的项目结构如下 处理来自客户端的传入请求的 Web 服务器 向用户提供一些建议的分析模块 我们决定保持这些模块完全独立 并将它们移动到不同的 docker 容器中 当用户的查询到达网络服务器时 它会向分析模块发送另一个查询以获取推荐
  • 如果我们不需要位图,是否必须显式回收它?

    位图有一个recycle方法 但是如果我们不再需要它 是否必须显式调用它 例如 一个ImageView现在有一个位图 当用户单击按钮时 它将为 ImageView 设置一个新的位图 在分配新位图之前我们是否必须回收原始位图 是的 如果您的目
  • 如何在ggplot的facet_grid函数中应用下标

    我想使用 ggplot 绘制空气污染物与出生体重变化之间的关联结果 95 CI 我的数据格式是这样的 variable exposure period coef coef lb coef ub PM10 entire pregnancy 2
  • 如何从在 Cron 作业上运行的 Python 解锁 Gnome 密钥环?

    我正在连接一个 Python 脚本来与 cron 一起运行 在 Ubuntu 12 04 上 但身份验证不起作用 cron 脚本访问几个服务 并且必须提供凭据 存储这些凭证keyring很简单 只不过当 cron 作业实际运行时 无法检索凭
  • Map:如何获取与某个值关联的所有键?

    给定一个 Map 如何查找与特定值关联的所有键 例如 Map
  • 背包多重约束

    我有一个动态规划问题 我花了几个小时研究但没有结果 第一部分很简单 你有一背包物品 你必须最大化这些物品的价值 同时将它们保持在一定的重量以下 问题的第二部分是相同的 只是现在也有一个项目限制 例如 您可以放入袋子中的物品的最大价值是多少