针对特殊分配问题的高效解决方案

鉴于:

- 一组项目,每个项目都有放入给定容器类型的成本.

- 一组容器类型,每个容器类型都有许多可用容器.

例:

金额*集装箱类型:5*A,3*B,2*C.

物品(成本):

3*X(A = 2,B = 3,C = 1)

2*Y(A = 5,B = 2,C = 2)

1*Z(A = 3,B = 3,C = 1)

问题:

找到物品放入容器的最佳位置,以便降低成本.为简单起见,仅将项目放入单一类型的容器中.

我尝试使用匈牙利方法来解决问题,但是运行时间为O(n³),对于大问题(例如,100000项)来说,这是非常令人望而却步的.

我目前的解决方案是一种贪婪的方法,只需按成本(asc)对项目 - 容器组合进行排序,并在O(n log n)中为第一个容器分配足够的数量.

有更好的解决方案吗？

这个问题是Knapsack问题的一个变种,从维基百科页面开始并从那里继续阅读.

众所周知,贪心算法是一个相当不错的近似,所以你可能已经足够好了.