请教一个问题，不知是不是多背包问题。

有m种背包，每种背包的容量为A[i]，数量为B[i]，例如：
int A[] = { 500, 400, 100, 30 };  // 背包容量
int B[] = {   1,  32,  15,  1 };  // 背包数量

现有n种物品，每种物品的重量为C[i]，数量为D[i]，例如：
int C[] = { 320, 200, 95, 70, 52, 28 };  // 物品重量
int D[] = {  11,   8, 12,  1, 11, 10 };  // 物品数量

已知0＜m＜10，0＜n＜30，且物品的总重量不会超过Int32所能表示的范围。

现求用这些背包能否把这些物品全部装入。
如不能，输出“无法全部装入”。
如可以，求最节省的方案，即背包总容量最少，如有多种解答，任意输出一种即可。

例如，一种方案是：
10 * (400 : 320 + 52 + 28)
 1 * (400 : 320 + 70)
 4 * (400 : 200 * 2)
12 * (100 : 95)
 1 * (100 : 52)
背包总容量是 (10 + 1 + 4) * 400 + (12 + 1) * 100，不知是不是最节省的。

求思路，用伪代码表示，或用C++、Java、C#、VB表示均可，请各位大侠指教，谢谢！

6 个解决方案

#1

围观算法中

#2

lz帮你顶下。。

#3

可以转换成A*B个背包，装C*D个物品的问题？？

#4

应该是NP的问题，求最优的话恐怕只能靠搜索，用分支限界试试。说实话对于NP的问题，我知之甚少，没有太多剪枝的经验。如果剪枝做得好，小规模的NP也可以求最优解。

#5

建议楼主看一下，背包九江：
http://download.csdn.net/source/2329943

#6

剪枝我了做不来。看了《背包九讲》，不过没有找到需要的内容。还是谢谢大家，结贴。