如何找到合适的配方

Question

假设我有1000种原料，每种原料所含营养成分不同，而且价格不同

现在需要从中最多挑选4种原料，混合获得特定指标新产品（例如要求新产品fat>=6,protein>=11,Ca>=0.75）。

混合配方肯定会有很多种，需要从中挑选价格尽量低的配方。

混合计算采用加权平均，如50%的m_1+50%的m_2==>{fat:5.5,protein:10.75,Ca:0.75,price:150}

如果暴力计算，时间复杂度会达到O(1000^4)，这样能获得最优解。如何在兼顾时间的情况下，获取近似最优解呢？能有Python的解决方法最好。多谢多谢~

Answer 1

我的思路是，这种计算你可以使用多进程
以m_1为必添加作为条件，开启一个进程，其它三种材料排列组合(排除m_1)，进行计算
以m_2为必添加作为条件，开启一个进程，其它三种材料排列组合(排除m_1,m_2)，进行计算
......
以m_10为必添加作为条件，开启一个进程，其它三种材料排列组合(排除m_1~m_10)，进行计算
假设开启了10个进程，可以根据你内存和cpu能承受的程度，尽可能地开启进程数，把结果汇总。
当然此时若有一个进程结束了。就重新读入进度从m_11开始往上加。
假设你开启了10个进程，那么总时间就缩短到了原时间地十分之一。当然我只是说思路，并没有实测。