这是一个创建于 850 天前的主题，其中的信息可能已经有所发展或是发生改变。
各位大佬们，请教个算法问题哈：
背景是这样的： 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 等求解器硬撸最优解 |
Select Language