多个背包问题

Question

是0-1背包问题（http://www.wutianqi.com/?p=539）的延伸，与0-1背包问题的不同点在于把一个背包换成了多个背包，大致意思是有一堆物品放入n个背包中，要使其价值最大，应该怎么放

这个问题进一步延伸是不考虑n个背包价值最大化，而是要使得n各背包的价值尽可能相同。

如果采用枚举的话肯定可以得出结论，但是代价太高

Answer 1

首先回顾一下0-1背包，dp[i][j]代表前i个物品花费的cost为j，所得到的最大的value。现在有多个背包了，于是再加一个维度，dp[i][j][k]表示前i个物品放到j个背包里，第j个背包花费的cost为k，所得到的最大的value。