求大佬们推荐个算法，解决业务问题（最优商品购买组合问题）

[oktango]

各位大佬们，请教个算法问题哈：

背景是这样的： 1 、有一堆的待购买的商品 ，需要从商家处进行采购，从商家进行采购，需要运费和商品价格。运费的计算规则和商品的总重量以及运距有关系。 2 、有好几家商店，每家店的位置不同，可售卖的商品不一样，同一商品的价格也不一样。

除了暴力枚举外，有没有什么算法，可以求出一个最优解，花最少的钱（运费+商品价格），把东西买回来呀。

[learningman]

背包问题

[cyrbuzz]

遗传算法？

[paradoxie]

就是背包吧

[bsg1992]

动态规划

[sillydaddy]

我觉得一个关键的点是：运费计算规则是什么样的，运费与总重量有什么关系。

先看一个简单的情形：对于同一家商店，运费与商品的重量成正比。
比如商店 A ，1000kg 商品，运费是 1000 。那么商店 A 出售的每件商品，费用=商品价格+商品重量*1 元 /kg 。也就是说每件商品的含运费价格是可以计算出来的。比如一个小吃，进价 10 元，重量 1kg ，那么含运费价格=10+1=11 元。

单一商品在每个商店的含运费价格都可以计算出来，那么，对于这个商品，比较含运费价格，从最低的商店进货就行，数量不够就继续从第二低的商店进，直到数量足够。

既然单一商品可以这样做，那么所有的商品都可以这样做。所需要的只是把所有商品的含运费价格计算出来。

但实际生活中，运费跟重量并不是简单的线性关系(比如运输费与重量是分段的线性关系，图形上看是多段折线)。对于非线性的，我暂时还没想到有啥合适的算法，动态规划和背包算法应该是不合适的。

[yehoshua]

没有特殊运费规则情况下，枚举就比较好。每种商品单独计算从不同商家购买的价格，包括运费。选择价格最低的供应商。程序复杂度也不高。

[bsg1992]

@bsg1992
仅从现有描述的条件下来看。
只需要把 商品价格 运费 距离 重量 商家 提前计算好 缓存起来 直接查询就可了

[bybyte]

参考背包九讲

[dayeye2006199]

这个要看运费的计算是不是线性的。
如果是线性的，就是比较简单的背包问题求解。

如果不是线性的，就比较复杂，可以考虑启发式算法

[wingor2015]

想不到啥好办法，估计只能试试启发式算法了

[Aganzo]

这种业务问题怕是没那么容易去简化，例如阶梯式进价及运费：
1, A 商品 10 件起售，单价 1 元。满 100 件，单价 0.5 元（需采购 60 件）。订单满 1000 元，整体 98 折或送 B 商品 10 件。
2 ，满 10KG 商品，闪送运费 10 元 /公里，满 100KG ，金杯运费 50 元 /公里，满 10T ，货车上门 100 元 /公里。不满一车按一车计算。
建议直接上 Gurobi 等求解器硬撸最优解