3

好的快速概述

我研究过背包问题

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

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

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

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

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

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

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

例子

外袋：

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

内袋：

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

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

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

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

谢谢你提供的所有帮助

-扎克

4

2 回答 2

2

好吧，背包是 NP 难的，所以我很确定这也是 NP 难的（如果不是这样，你可以只用一个外袋来解决背包问题。）所以对于一个完全最优的解决方案，您可能只能搜索所有组合。所以你想要的程序的大纲就像

 for each possible combination
 do
   if current combination is better than best previous
      save current combination as best so far
   fi
 od

并且运行时间将是指数级的。不过，这听起来像是您可以通过动态编程获得近似解决方案。

于 2009-04-23T18:19:00.820 回答
0

考虑使用Prolog进行逻辑编程。它有多种实现，包括单声道（.NET）上的P# 。有一点学习曲线，但是一旦你习惯了它，它就几乎可以解决这种问题了。

希望这可以帮助。干杯!

链接到P#

于 2009-04-23T20:27:17.157 回答