algorithm - 容量为 y、x*y 项目的 x 箱子，最大化总分，其中每个(项目，箱子)对都有一个相关联的分数

Question

x bins, each with capacity y
x*y items
each (item, bin) pair has an associated score

在给定上述标准的情况下，是否有一种标准算法可以最大化总分？

Answer 1

这只是背包问题的变体，很常见:http://en.wikipedia.org/wiki/Knapsack_problem

---

在背包问题中，复杂度是O(2^n)，这就是O(k^n)，其中k是箱数。

---

解决方案:对于背包问题，您可以将每种可能性写成带有 0 和 1 的数字，其中 0 表示该位置的元素不在包中，1 表示在包中。

这个问题类似，但是0和1是不够的，你必须知道元素在哪个袋子里，所以你必须记住袋子的位置。

例如，如果你有 6 个项目，你可以将其写成这个数字(或数组):

005110

这可能意味着第一个和第二个项目不在任何包中，第三个在第 5 个包中，下一个在第一个包中，下一个在第一个包中，下一个不在任何包中。

---

工程推荐流程:创建您自己的完全可行的背包问题，然后将其重写为该问题。 (因为背包问题基本上就是这个只有一个bin的问题)