背包多重约束

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(使用前将#替换为@)

背包多重约束 的相关文章

  • 如何使用哈希表在最小堆上实现 O(1) 删除

    在某处阅读以下声明 可以使用附加的哈希表来快速删除 最小堆 问题 gt 如何组合priority queue and unordered map这样我就可以实现上面的想法了 include
  • 在 Python 中删除表达式树及其每个子表达式树中第一个元素周围的括号

    目标是实现简化操作 删除表达式树及其每个子表达式树中第一个元素周围的括号 其中表达式作为括在各个括号中的字符串输入给出 这必须适用于任意数量的括号 例如 12 3 45 6 gt 123 45 6 删除 12 周围的括号 然后删除 45 周
  • 算法:最大计数器

    我有以下问题 您有 N 个计数器 最初设置为 0 并且您对它们有两种可能的操作 increase X 计数器 X 加 1 max counter 所有计数器都设置为任何计数器的最大值 给出一个包含 M 个整数的非空零索引数组 A 该数组代表
  • 给定与总和匹配的长度的唯一 3 位数字 (-1,0,1) 序列的数量

    假设您有一个长度为 n 即空格数 的垂直游戏板 你有一个三面骰子 有以下选项 前进一 停留和后退 如果您低于或高于棋盘游戏空间的数量 则该游戏无效 一旦到达棋盘末端 唯一有效的动作就是 停留 给定确切的骰子投掷次数 t 是否可以通过算法计算
  • 添加到数组连续数字

    这是我向SO提出的第一个问题 我希望能答对 在 PHP 中 如果你不会 Python 或伪语言也可以 给定一个包含 n 个元素的数组 old array 1 2 3 5 7 8 9 20 21 23 29 我需要向新数组添加连续数字 如果不
  • 给定两个(大)点集,我如何有效地找到彼此最接近的点对?

    我需要解决一个计算问题 该问题归结为搜索两个集合之间最接近的点对 问题是这样的 给定欧几里德空间中的一组点 A 和一组点 B 找到所有对 a b 使得 b 是 B 中与 a 最近的点 a 是 A 中与 b 最近的点 集合 A 和 B 的大小
  • 4 x 3 锁图案

    我遇到了这个 它要求计算在 4x3 网格中可以制作特定长度的锁定图案的方式数 并遵循规则 可能有些点不能包含在路径中 有效的模式具有以下属性 图案可以使用第一次接触的点序列来表示 与绘制图案的顺序相同 从 1 1 到 2 2 的图案与图案不
  • 如何使用KDTrees实现最近邻搜索?

    所以 我正在实施一个KD Tree http en wikipedia org wiki Kd tree进行最近邻搜索 我已经构建了树部分 但我认为我没有完全理解搜索部分 关于遍历树来搜索邻居 维基百科文章如下 Starting with
  • cordova 使用什么 js“引擎”?

    Cordova 使用什么 JS 引擎 它是特定于平台的还是跨所有平台的一个标准 意味着 iOS 的 safari 和 Android 的 chrome 以及 Windows 可能的 IE 标准 或者跨所有平台的 Cordova JS 引擎
  • 在 Java 中实现排列算法的技巧

    作为学校项目的一部分 我需要编写一个函数 该函数将接受整数 N 并返回数组 0 1 N 1 的每个排列的二维数组 该声明看起来像 public static int permutations int N 该算法描述于http www usn
  • 如何求解:T(n) = T(n - 1) + n

    我已经解决了以下问题 T n T n 1 n O n 2 现在 当我解决这个问题时 我发现界限非常松散 我是否做错了什么 或者只是这样 您还需要一个递归关系的基本情况 T 1 c T n T n 1 n 为了解决这个问题 您可以首先猜测一个
  • 线性代数如何在算法中使用?

    我的几个同行都提到 学习算法时 线性代数 非常重要 我研究了各种算法并学习了一些线性代数课程 但我没有看到其中的联系 那么线性代数如何应用在算法中呢 例如 图的连接矩阵可以带来哪些有趣的事情 三个具体例子 线性代数是现代 3D 图形的基础
  • 将嵌套字典中的所有键从camelCase转换为snake_case

    我有一本类似这样的字典 firstName abc lastName xyz favoriteMovies Star Wars The lone ranger favoriteCountries country China capitalC
  • 如何高效地在屏幕上精确绘制N个点?

    这听起来是一个简单的问题 但我发现要获得良好的性能是非常棘手的 我提出的第一个算法是随机绘制点 从一组中检查是否已绘制 否则绘制 如果我们只绘制几个点 那么这种方法效果很好 但当我们接近填满屏幕时 速度会灾难性地减慢 我想出的最好的方法是构
  • 快速求解子集和

    考虑这种解决子集和问题的方法 def subset summing to zero activities subsets 0 for activity cost in activities iteritems old subsets sub
  • 使用主方法求解 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
  • 通过分布式数据库聚合作业优化网络带宽

    我有一个分布式 联合数据库 结构如下 数据库分布在三个地理位置 节点 每个节点集群有多个数据库 关系数据库是 PostgreSQL MySQL Oracle 和 MS SQL Server 的混合体 非关系数据库是 MongoDB 或 Ca
  • 检索受“rowspan”影响的行的列索引的最有效方法是什么?

    考虑下表 table thead tr th th th A th th B th th C th tr thead tbody tr th 1 th td Apples td td Oranges td td Pears td tr tb
  • 如何将无向图转换为 DAG?

    The 维基页面 http en wikipedia org wiki Directed acyclic graph Relation to other kinds of graphs says 任何无向图都可以通过为其顶点选择总顺序并将每
  • 固定大小集以包含给定集的最大数量

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

随机推荐

  • 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
  • 背包多重约束

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