算法：类似N SUM问题求解

Question

题目描述

类似N SUM的问题，想法来源于工作中遇到的一个小任务，抽象出来的：
有m个商品，给出每个商品单价P1,P2,P3,...,Pm
现在有n个订单，每个订单的总额为S1,S2,S3,...,Sn（P<S)
现要求为每个订单总额Sn匹配尽可能多的产品价格*数量组合，始得等式左右两边尽可能接近：
Sn=P1数量+p2数量+...

解决思路

用python实现解决

Answer 1

这不就是背包问题吗

Answer 2

一个经典的QAP问题，实现的方法有很多种，针对具体数据的不同可以有不同优化的方式。
如果实现一个通用版本，可以采用线性规划的方法求解。

Python 可以通过 cvxpy 实现