问题标签 [subset-sum]

这是我的一类编程项目，我不是在寻找答案，而是在寻找对问题的更多解释。我真的不明白在问什么。。

这是另一个输入/输出：输入：1 2 3 3 4 5 输出：1 2 3 3

我不明白我们是如何得到这个输出的，有人可以更简单地向我解释一下吗？谢谢

这是问题陈述：

给定一个整数列表 L 和一个整数 S，生成所有元素加起来为 S 的子列表。

这是我的解决方案：

因此，在我运行它并被要求输入目标之后，我尝试这样做getsub([1,2,5,6],X,7) 以获取其元素加起来为 7 的所有子集，但我得到一个No Solution, 和 check 子句中变量的警告LR，变量是不受约束。我不确定我做错了什么，或者是否有更简单的解决方案。任何帮助表示赞赏。

我正在研究一个必须处理背包/子集和问题的特殊情况的问题。问题如下：

您有一组随机递减的捆绑包大小，例如：{47, 35, 22, ...}. 您的价值是小部件的数量，例如：#widgets = 33。找到可以构成捆绑小部件数量的最少捆绑数量。如果无法返回等于数量的集合，则返回 null。

• 示例 1：
  • 捆绑尺寸：46、25、12、4、3
  • 数量：30
  • 返回值：{46:0, 25:0, 12:2, 4:0, 3:2}（捆绑包大小：捆绑包数）
• 示例 2：
  • 捆绑尺寸：46、25、12、4、3
  • 数量：17
  • 返回值：{46:0, 25:0, 12:0, 4:2, 3:3}
• 示例 3：
  • 捆绑尺寸：46、25、12、4、3
  • 数量：47
  • 返回值：{46:0, 25:1, 12:1, 4:1, 3:2}
• 示例 4：
  • 捆绑尺寸：46、25、12、4、3
  • 数量：5
  • 返回值：空

这个问题怎么解决？

我用 C# 编写了一个程序，该程序完成了足够接近的工作，但在 for 循环中重置了一个索引以转储无法与集合的其余部分一起使用的包大小。如果要求它走多远，将发布来源。

要求的代码：

这是我们算法期末考试的一道题。这是逐字逐句的，因为教授让我们把考试副本带回家。

1. （20 分）令 I = {r1,r2,...,rn} 是一组n 个任意正整数，并且I中的值是不同的。 我没有按任何排序顺序给出。假设我们想要找到I'的子集，使得I '中所有元素的总和正好是 100*ceil(n^.5) （ I 的每个元素最多可以在I'中出现一次）。提出一个 O( n ) 时间算法来解决这个问题。

据我所知，它基本上是背包问题的一个特例，也称为子集和问题......这两者都在 NP 中，理论上不可能在线性时间内解决？

那么......这是一个诡计问题吗？

这篇 SO 帖子基本上解释说，如果权重有界，则可以进行伪多项式（线性）时间近似，但在考试问题中，权重不受限制，无论哪种方式，考虑到考试的整体难度，我都会感到震惊如果教授希望我们知道/想出一个模糊的动态优化算法。

我有一个菜单 dict 项目作为键和价格作为值。可能存在比单个项目便宜一点的项目组合。例如：

现在假设我订购了一些物品，那么输出将是给定订单的最小数量：

这是我尝试的所有价格的代码，我将用作生成器：

但是当我运行它时它说类型错误：

这是表格T：-

以下是一个虚构的sql

预期结果是：-

（一个）

(乙)

（C）

'A' 案例是最优选的！

我知道这种情况与组合有关。

在现实世界中 - 客户从商店获取物品，并且由于他与商店之间的协议，他每周五付款。付款金额不是物品的确切总和，例如：他得到 5 本书 50 欧元（= 250 欧元），周五他带来 150 欧元，所以前 3 本书是完美匹配的 - 3 * 50 = 150。我需要找到这3本书的ID！

任何帮助，将不胜感激！

这个问题是在亚马逊采访中被问到的——

给定一个正整数数组，您必须找到不能从数组中的数字之和形成的最小正整数。

例子：

我所做的是：

1. 对数组进行排序
2. 计算前缀和
3. 遍历 sum 数组并检查下一个元素是否小于 1 大于 sum 即 A[j]<=(sum+1)。如果不是这样，那么答案将是sum+1

但这是 nlog(n) 解决方案。

面试官对此并不满意，并在不到 O(n log n) 的时间内提出了解决方案。

给定一个方程

比如 2(p ₁ ) + 3(p ₂ ) + 7(p ₃ ) >= 257

我需要找到 p ₁、 p ₂、 p _{3的所有可能组合，这样上述陈述是正确的，并且在所有 x n}都已知 的情况下，得到的总和（等式的左侧）是最小的。

我尝试为一般情况查找算法，例如

(x ₁ )(p ₁ ) + (x ₂ )(p ₂ ) + (x ₃ )(p ₄ ) + ... + (x _n )(p _n ) >= 目标

我遇到了背包问题和子集​​和算法解决方案，但它们并不完全像这个问题。

_{我在 Python 3.x 中使用具有 p n}下界值的算法之前尝试过，但它仍然以 O（荒谬）的时间复杂度运行。

显然这里的所有数字都是自然数，否则将有无限的解决方案。

如果我有一个数字数组和一个总计数组元素的总和列表，那么确定总和中包含哪些元素的最有效方法（或至少不是蛮力破解）是什么？

一个简化的示例可能如下所示：

数组 = [6, 5, 7, 8, 6, 12, 16] 总和 = [14, 24, 22]

我想知道：

14 包括 8、6

24 包括 5、7、12

22 包括 6、16

http://jsfiddle.net/tTMvP/

我确实知道总会有至少一个正确的答案，我只需要检查数字，我不需要配对有重复的索引，只需配对与总数相关的值。是否有解决此类问题的既定功能？

这只是一个 javascript 问题，因为这是我正在编写解决方案的语言，这更像是通过 Javascript 过滤的一般数学相关问题。如果这不是适当的论坛，我欢迎重定向到适当的堆栈交换站点。

我试图弄清楚如何修改子集和问题的代码，以便我可以打印出它最终返回 True 时找到的值。我当前的实现递归地工作并利用记忆，但我不知道如何改变它来存储并最终返回达到所需总和的路径。

我已经尝试放弃它的递归性并改用迭代，但我不知道如何在我的 for 循环中布置代码以处理我们不使用下一个值和何时使用的情况它。

注意：在这个实现中，值只能使用一次，不确定起源“子集和”问题是否强制执行......

任何有关如何转换它的帮助或提示将不胜感激。我这样做是为了为即将到来的面试做练习。