背包问题和的可能组合？
好吧，快速概述
我已经研究了背包问题
http://en.wikipedia.org/wiki/Knapsack_problem< /a>
我知道这是我的项目所需要的，但我的项目的复杂部分是我需要在一个主麻袋内放置多个麻袋。
容纳所有“袋子”的大背包只能携带 x 个“袋子”（例如 9 个）。 每个包都有不同的价值；
- 重量、
- 成本、
- 尺寸
- 、容量
等，所有这些值都是整数。 让我们假设从 0 到 100。
内袋也将被分配一个类型，并且外袋内只能有一个该类型，尽管程序输入将被赋予多个相同类型。
我需要指定主包可以容纳的最大重量，并且较小包的所有其他属性需要按加权值进行分组。
示例
外袋
- ：可容纳 9 个较小的袋子
- 重量不超过 98 [每边各 5 个]
- 必须容纳每种类型中的一个，一次只能容纳每种类型中的一个。
内袋：
- 成本，按 100%
- 尺寸加权，按 67%
- 容量加权，按 44% 加权
该程序将给出多个袋子的输入，然后必须计算出较小袋子的组合以放入较大袋子中，将有根据输入有多种解决方案，程序将为我输出最佳解决方案。
我想知道你们认为我解决这个问题的最佳方法是什么。
我将使用 Java 或 C# 对其进行编程。 我很想用 PHP 对其进行编程，但我担心该算法对于 Web 服务器来说效率非常低。
感谢您提供的任何帮助
-Zack
Alright quick overview
I have looked into the knapsack problem
http://en.wikipedia.org/wiki/Knapsack_problem
and i know it is what i need for my project, but the complicated part of my project would be that i need multiple sacks inside a main sack.
The large knapsack that holds all the "bags" can only carry x amount of "bags" (lets say 9 for sake of example). Each bag has different values;
- Weight
- Cost
- Size
- Capacity
and so on, all of those values are integer numbers. Lets assume from 0-100.
The inner bag will also be assigned a type, and there can only be one of that type within the outer bag, although the program input will be given multiple of the same type.
I need to assign a maximum weight that the main bag can hold, and all other properties of the smaller bags need to be grouped by weighted values.
Example
Outer Bag:
- Can hold 9 smaller bags
- Weight no more than 98 [Give or take 5 either side]
- Must hold one of each type, Can only hold one of each type at a time.
Inner Bags:
- Cost, Weighted at 100%
- Size, Weighted at 67%
- Capacity, Weighted at 44%
The program will be given an input of multiple bags, and then must work out combinations of Smaller Bags to go into the larger bag, there will be multiple solutions depending on the input, and the program would output the best solutions for me.
I am wondering what you guys think the best way for me to approach this would be.
I will be programming it in either Java, or C#. I would love to program it in PHP but i'm afraid the algorithm would be very inefficient for web servers.
Thanks for any help you can give
-Zack
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
好吧，好吧，背包是 NP 难的，所以我很确定这也将是 NP 难的（如果不是，你可以通过只用一个外袋来解决背包问题。）因此，对于一个完全最优的解决方案，您可能只能搜索所有组合。 所以你想要的程序的轮廓将是这样的，
并且运行时间将是指数级的。 不过，听起来您也许可以通过动态编程获得接近的解决方案。
Okay, well, knapsack is NP-hard so I'm pretty certain this will be NP-hard as well (if it weren't you could solve knapsack by doing this with only one outer bag.) So for an exactly optimal solution, you're probably going to be able to do no beter than searching all combinations. So the outline of the program you want will be like
and the run time will be exponential. It sounds, though, like you might be able to get a near solution with dynamic programming.
考虑使用 Prolog 进行逻辑编程。 它有多种实现，包括 Mono (.NET) 上的 P#。 有一点学习曲线，但是一旦你习惯了它，它对于解决此类问题来说几乎是独一无二的。
希望这可以帮助。 干杯!
链接到P#
Consider using Prolog for your logical programming. There's multiple implementations of it including P# on mono (.NET). Theres a bit of a learning curve, but once you get used to it, it's pretty much in a league of its own for this kind of problem solving.
Hope this helps. Cheers!
link to P#