背包问题和可能的组合？ [英] Possible Combination of Knapsack problem and?

问题描述

好吧简要概述

我看着背包问题。

的 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.

大背包的拥有所有的包装袋只能携带的袋X量（可以说9了一个例子）。每个包包都有不同的价值观;

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

等等，所有这些值都是整数。让我们从0-100承担。

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.

---

示例

外袋：

• 可容纳9小包包


• 重量不超过98 [给予或采取5两侧]


• 必须持有每种类型的，只能持有每种类型在一个时间中的一个。

内蒙古手袋：

• 成本，100％

加权
• 尺寸，在67％


• 容量，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.

我将在任一Java或C＃编程它。我很想给它的PHP程序，但我担心的算法将是Web服务器的效率非常低。

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

推荐答案

好吧，背包是一个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

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

和运行时间将指数。这听起来，不过，就像你也许可以得到与动态编程。

and the run time will be exponential. It sounds, though, like you might be able to get a near solution with dynamic programming.

这篇关于背包问题和可能的组合？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！