各位大佬们,请教个算法问题哈:
背景是这样的: 1 、有一堆的待购买的商品 ,需要从商家处进行采购,从商家进行采购,需要运费和商品价格。运费的计算规则和商品的总重量以及运距有关系。 2 、有好几家商店,每家店的位置不同,可售卖的商品不一样,同一商品的价格也不一样。
除了暴力枚举外,有没有什么算法,可以求出一个最优解,花最少的钱(运费+商品价格),把东西买回来呀。
1
learningman 2022-07-26 18:16:23 +08:00 via Android
背包问题
|
2
cyrbuzz 2022-07-26 18:27:21 +08:00
遗传算法?
|
3
paradoxie 2022-07-26 19:22:48 +08:00
就是背包吧
|
4
bsg1992 2022-07-26 20:12:55 +08:00
动态规划
|
5
sillydaddy 2022-07-26 20:39:14 +08:00
我觉得一个关键的点是:运费计算规则是什么样的,运费与总重量有什么关系。
先看一个简单的情形:对于同一家商店,运费与商品的重量成正比。 比如商店 A ,1000kg 商品,运费是 1000 。那么商店 A 出售的每件商品,费用=商品价格+商品重量*1 元 /kg 。也就是说每件商品的含运费价格是可以计算出来的。比如一个小吃,进价 10 元,重量 1kg ,那么含运费价格=10+1=11 元。 单一商品在每个商店的含运费价格都可以计算出来,那么,对于这个商品,比较含运费价格,从最低的商店进货就行,数量不够就继续从第二低的商店进,直到数量足够。 既然单一商品可以这样做,那么所有的商品都可以这样做。所需要的只是把所有商品的含运费价格计算出来。 但实际生活中,运费跟重量并不是简单的线性关系(比如运输费与重量是分段的线性关系,图形上看是多段折线)。对于非线性的,我暂时还没想到有啥合适的算法,动态规划和背包算法应该是不合适的。 |
6
yehoshua 2022-07-26 20:42:46 +08:00 via Android
没有特殊运费规则情况下,枚举就比较好。每种商品单独计算从不同商家购买的价格,包括运费。选择价格最低的供应商。程序复杂度也不高。
|
8
bybyte 2022-07-27 01:24:19 +08:00 via Android
参考背包九讲
|
9
dayeye2006199 2022-07-27 15:57:02 +08:00 via Android
这个要看运费的计算是不是线性的。
如果是线性的,就是比较简单的背包问题求解。 如果不是线性的,就比较复杂,可以考虑启发式算法 |
10
wingor2015 2022-07-27 16:22:25 +08:00
想不到啥好办法,估计只能试试启发式算法了
|
11
Aganzo 2022-07-27 17:49:37 +08:00
这种业务问题怕是没那么容易去简化,例如阶梯式进价及运费:
1, A 商品 10 件起售,单价 1 元。满 100 件,单价 0.5 元(需采购 60 件)。订单满 1000 元,整体 98 折或送 B 商品 10 件。 2 ,满 10KG 商品,闪送运费 10 元 /公里,满 100KG ,金杯运费 50 元 /公里,满 10T ,货车上门 100 元 /公里。不满一车按一车计算。 建议直接上 Gurobi 等求解器硬撸最优解 |