现有商品 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 倍来求解吗？
 |
1
tmsdy0404 OP 坐等大佬解惑~~~~
|
 |
2
wa007 Mar 19, 2022
相比多重背包，你这个题目一共有 M 个背包，套用多重背包的做法开销实在太大了。
这应该是个业务问题，不是个算法问题吧。 |
|
3
wa007 Mar 19, 2022
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 中找不到满足条件的发票为止。 时间复杂度就不算了，随机数据的耗时肯定是大大小于最差复杂度的。如果数据量不大，应该是可行的。 |
|
4
tmsdy0404 OP @wa007 量有点大啊，没办法把集合 A 的所有组合全部弄出来。
这是实际的数据，虽然商品各类不多，但有的商品数量是 40000 个， 单这个商品就有 2 的 40000 次方-1 种组合，这个量级没法弄吧  |
|
5
wa007 Mar 19, 2022
你看下背包算法，实现第一步不需要「 2 的 40000 次方-1 种组合」，复杂度主要跟 `PN` 有关
|
Select Language