求助，一个比多重背包还要复杂一点的问题。

[tmsdy0404]

现有商品 N(N<100)类，第 i 类商品的数量为 C[i],单价为 P[i]， 即第 i 类商品的总价格为 C[i]*P[i]。 则所有商品的总价格 PN 为：

另有发票 M(M<N)张。 第 k 张发票的金额为 V[k]。 所以发票的总金额 PM 为：

且 PM = PN 。

求如何分配商品，使其总金额刚好对应上每一张发票金额。 （允许有正负 1 元的误差，我也觉得不可理解，但事实就是这样）

^^^^^^^^^^^^^^说人话的分割线^^^^^^^^^^^^^^^^^^^^^^^

上面说的可能不太清楚，我直接举例：

绿色区域就是要求解的值。可能有很多解，只需要求出来使每个发票金额刚好满足就可以。

个人感觉，如果把每一张发票金额去按多重背包问题求最优，不一定能保证所有发票整体最优。 另外，我这个价格也就是背包问题中的体积，是有小数的，难道要全部放大 100 倍来求解吗？

[tmsdy0404]

坐等大佬解惑~~~~

[wa007]

相比多重背包，你这个题目一共有 M 个背包，套用多重背包的做法开销实在太大了。
这应该是个业务问题，不是个算法问题吧。

[wa007]

1. 初始化
1 ）把所有商品放入集合 A
2 ）把所有发票放入集合 B

2. 迭代
1 ）调用多重背包算法，判断当前的集合 A 都可以组成和为哪些金额的发票，输出数组 A_array ，A_array[i] = True 表示 金额为 i 的发票可以由集合 A 中的某些商品求和得到，A_array[j] = False 表示金额 j 的发票不能由 A 中的商品求和得到。
2 ）从小到大遍历集合 B 中的发票，假设当前是金额为 i 的发票，判断 A_array[i] 如果是 True ，就把 i 从集合 B 中删除，同时加入 {j - i for j in B if j > i}（因为你下次可以组成金额为 j-i 的发票，然后把 j 删除，i 再放回 B ），再把 A 中对应的商品剔除。如果 A_array[i] = False ，就继续遍历。如果 B 中全都是 False ，就结束。PS：如果你抽到了 j-i ，就要把 j 删除，加入 i ，对每个发票打个标记，表示如果删除当前发票，需要加入哪些发票。
3 ）直到 A 或者 B 为空，或 B 中找不到满足条件的发票为止。

时间复杂度就不算了，随机数据的耗时肯定是大大小于最差复杂度的。如果数据量不大，应该是可行的。

[tmsdy0404]

@wa007 量有点大啊，没办法把集合 A 的所有组合全部弄出来。
这是实际的数据，虽然商品各类不多，但有的商品数量是 40000 个，
单这个商品就有 2 的 40000 次方-1 种组合，这个量级没法弄吧



[wa007]

你看下背包算法，实现第一步不需要「 2 的 40000 次方-1 种组合」，复杂度主要跟 `PN` 有关