问题标签 [knapsack-problem]

有没有人知道规范 CS 问题的良好参考？

我在想诸如“分类问题”、“装箱问题”、“劳苦推销员问题”之类的东西。

编辑：首选网站

假设您有一个由一堆固定大小的块组成的大文件。这些块中的每一个都包含一些可变大小的记录。每条记录必须完全适合单个块，然后根据定义，这些记录永远不会大于完整块。随着时间的推移，记录在这些块中添加和删除，因为记录来自这个“数据库”。

在某些时候，尤其是在可能将许多记录添加到数据库并删除了一些记录之后 - 许多块可能最终只被部分填充。

什么是一个好的算法来打乱这个数据库中的记录，通过更好地填充部分填充的块来压缩文件末尾不必要的块？

算法要求：

• 必须在原始文件的位置进行压缩，而不是暂时将文件从其起始大小最多扩展几个块
• 该算法不应不必要地干扰已经基本满的块
• 必须一次从文件读取或写入整个块，并且应该假设写入操作相对昂贵
• 如果记录从一个块移动到另一个块，则必须在从其起始位置删除之前将它们添加到新位置，以便在操作中断时不会因“失败”压缩而丢失记录。（假设这种记录的临时重复可以在恢复时检测到）。
• 可用于此操作的内存可能只有几个块的数量级，这仅占整个文件大小的很小百分比
• 假设记录大约为 10 字节到 1K 字节，平均大小可能为 100 字节。固定大小的块大约为 4K 或 8K，文件大约为 1000 个块。

好的快速概述

我研究过背包问题

http://en.wikipedia.org/wiki/Knapsack_problem

我知道这是我的项目所需要的，但我项目的复杂部分是我需要在一个主袋内有多个袋子。

装着所有“袋子”的大背包只能携带 x 个“袋子”（例如 9 个）。每个包都有不同的价值；

• 重量
• 成本
• 尺寸
• 容量

依此类推，所有这些值都是整数。让我们假设从 0-100。

内袋也将被分配一个类型，外袋中只能有一种类型，尽管程序输入将被赋予多个相同类型。

我需要指定主包可以容纳的最大重量，而小包的所有其他属性都需要按加权值分组。

例子

外袋：

• 可容纳 9 个较小的袋子
• 重量不超过 98 [两边各取 5 个]
• 每种必须持有一种，每次只能持有一种。

内袋：

• 成本，100% 加权
• 大小，权重为 67%
• 容量，权重为 44%

程序将输入多个袋子，然后必须计算出较小袋子的组合才能进入较大的袋子，根据输入会有多个解决方案，程序会为我输出最佳解决方案。

我想知道你们认为我解决这个问题的最佳方法是什么。

我将使用 Java 或 C# 对其进行编程。我很想用 PHP 对其进行编程，但我担心该算法对于 Web 服务器来说效率很低。

谢谢你提供的所有帮助

-扎克

我正在使用 VB.NET，我正在尝试提出一些算法或一些伪代码，或者一些 VB.NET 代码，它们可以让我执行以下操作（希望我能很好地解释这一点）：

我有 2 个集合对象，Cob1 和 Cob2。这些集合对象存储实现称为 ICob 的接口的对象。ICob 有 3 个属性。一个布尔值 IsSelected 属性、一个名为 Length 的属性，它返回一个 TimeSpan，以及一个 Rating 属性，它是一个短整数。

好的，现在 Cob1 有大约 100 个对象存储在集合中，而 Cob2 是一个空集合。我想要做的是从 Cob1 中选择对象并将它们复制到 Cob2。我希望在选择对象时遵守以下规则：

1. 我希望能够指定一个时间跨度，并且我希望选择足够多的对象以适应我指定的时间跨度（基于 Length 属性）。例如，如果我将 10 分钟的时间跨度传递给我的函数，它应该选择足够多的对象来填满整个 10 分钟的窗口，或者尽可能接近填满它。

2. 不应选择任何对象两次。

3. 具有较高等级（通过等级属性）的对象应该比其他对象更有可能被拾取。

4. 不应再次选择在过去 30 分钟内已选择的任何对象（以便每个对象最终将至少被选择一次），无论评级如何。

谁能给我一些关于如何实现这一目标的提示？提示可以是心理过程、VB.NET 示例代码、伪代码或任何其他可能对我有帮助的形式。

谢谢

编辑：

如果我透露我在现实生活中想要做的事情，也许这会对每个人都有帮助。

我正在为一个广播电台编写软件，它会自动选择要播放的音乐和广告，有点像计算机化的程序管理器。

长度表示声音字节（歌曲或广告）的长度，评级就是这样。如果这首歌很受欢迎，它会获得更多的播放时间。如果广告商支付更多的钱，那么它也会获得更多的播出时间。

所以我的程序应该选择播放20分钟左右的歌曲，然后选择一些广告播放5分钟左右。

希望这会有所帮助。

感谢大家的投入！

艾伦

有一个数字列表。
该列表将被分成 2 个大小相等的列表，总和的差异最小。必须打印总和。

在某些情况下，以下代码算法是否有错误？

我如何优化和/或 pythonize 这个？

问题来自http://www.codechef.com/problems/TEAMSEL/

我有一个总数为 540000 的数字列表。我想将此列表排序为 3 个列表，每个列表总计 180000。假设数字列表是一个平面文件，每个列表都有一个数字，那么最有效的编程方法是什么？线？

如果存在多个约束（例如，同时有体积限制和重量限制，其中每个项目的体积和重量不相关），我们得到多重约束背包问题，多维背包问题，或 m维背包问题。

我如何以最优化的方式对此进行编码？好吧，人们可以开发一种强力递归解决方案。可能是分支和绑定的.. 但基本上它在大多数情况下是指数级的，直到您进行某种记忆或使用动态编程，如果做得不好，这又会占用大量内存。

我面临的问题是这个

我有我的背包函数 KnapSack(Capacity, Value, i) 而不是常见的 KnapSack (Capacity, i)，因为我对这两个函数都有上限。有人可以指导我吗？或提供合适的资源来解决这些问题，以获得相当大的 n

还是这个NP完整？

谢谢

我正在用 Java 编写一个多线程应用程序，以提高顺序版本的性能。它是 0/1 背包问题的动态规划解决方案的并行版本。我有一个 Intel Core 2 Duo，在不同的分区上有 Ubuntu 和 Windows 7 Professional。我在 Ubuntu 中运行。

我的问题是并行版本实际上比顺序版本需要更长的时间。我在想这可能是因为线程都被映射到同一个内核线程，或者它们被分配到同一个内核。有没有办法可以确保每个 Java 线程都映射到一个单独的核心？

我已阅读有关此问题的其他帖子，但似乎没有任何帮助。

这是 KnapsackThread 类（它扩展了 Thread）的 main() 和所有 run() 的结尾。请注意，我使用 slice 和 extra 来计算 myLowBound 和 myHiBound 的方式确保每个线程不会在 dynProgMatrix 的域中重叠。因此不会有竞争条件。

更新：

我写了另一个版本的使用蛮力的背包。这个版本几乎没有同步，因为我只需要在单个线程执行结束时更新一个 bestSoFar 变量。因此，每个线程几乎应该完全并行执行，除了最后那个小的关键部分。

我运行这个而不是连续的蛮力，但仍然需要更长的时间。除了我的线程正在按顺序运行之外，我没有看到任何其他解释，因为它们被映射到同一个核心或同一个本机线程。

有没有人有任何见识？

这个问题比knapsack（或它的一种类型，没有值，只有正权重）更简单。问题在于检查一个数字是否可以是其他数字的组合。该函数应该返回trueor false。

例如，

112 和一个应该返回的列表{ 17, 100, 101 }，false同469一个列表应该返回true，35应该返回false，119应该返回true，等等......

编辑：子集总和问题比背包更准确。

我正在寻找有效的多背包问题的伪代码解决方案（优化语句位于页面的中间）。我认为这个问题是 NP Complete，所以解决方案不需要是最优的，如果它相当有效且易于实施，那将是好的。

问题是这样的：

• 我有许多工作项目，每个项目都需要不同（但固定且已知）的时间来完成。
• 我需要将这些工作项分成组，以便拥有最少数量的组（理想情况下），每组工作项花费的时间不超过给定的总阈值 - 例如 1 小时。

我对阈值很灵活 - 它不需要严格应用，但应该接近。我的想法是将工作项分配到 bin 中，每个 bin 代表阈值的 90%、80%、70% 等等。然后我可以将占 90% 的项目与占 10% 的项目进行匹配，依此类推。

有更好的想法吗？