V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
oktango
V2EX  ›  程序员

求大佬们推荐个算法,解决业务问题(最优商品购买组合问题)

  •  
  •   oktango · 2022-07-26 18:16:00 +08:00 · 1814 次点击
    这是一个创建于 836 天前的主题,其中的信息可能已经有所发展或是发生改变。

    各位大佬们,请教个算法问题哈:

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

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

    11 条回复    2022-07-27 17:49:37 +08:00
    learningman
        1
    learningman  
       2022-07-26 18:16:23 +08:00 via Android
    背包问题
    cyrbuzz
        2
    cyrbuzz  
       2022-07-26 18:27:21 +08:00
    遗传算法?
    paradoxie
        3
    paradoxie  
       2022-07-26 19:22:48 +08:00
    就是背包吧
    bsg1992
        4
    bsg1992  
       2022-07-26 20:12:55 +08:00
    动态规划
    sillydaddy
        5
    sillydaddy  
       2022-07-26 20:39:14 +08:00
    我觉得一个关键的点是:运费计算规则是什么样的,运费与总重量有什么关系。

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

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

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

    但实际生活中,运费跟重量并不是简单的线性关系(比如运输费与重量是分段的线性关系,图形上看是多段折线)。对于非线性的,我暂时还没想到有啥合适的算法,动态规划和背包算法应该是不合适的。
    yehoshua
        6
    yehoshua  
       2022-07-26 20:42:46 +08:00 via Android
    没有特殊运费规则情况下,枚举就比较好。每种商品单独计算从不同商家购买的价格,包括运费。选择价格最低的供应商。程序复杂度也不高。
    bsg1992
        7
    bsg1992  
       2022-07-26 20:49:55 +08:00
    @bsg1992
    仅从现有描述的条件下来看。
    只需要把 商品价格 运费 距离 重量 商家 提前计算好 缓存起来 直接查询就可了
    bybyte
        8
    bybyte  
       2022-07-27 01:24:19 +08:00 via Android
    参考背包九讲
    dayeye2006199
        9
    dayeye2006199  
       2022-07-27 15:57:02 +08:00 via Android
    这个要看运费的计算是不是线性的。
    如果是线性的,就是比较简单的背包问题求解。

    如果不是线性的,就比较复杂,可以考虑启发式算法
    wingor2015
        10
    wingor2015  
       2022-07-27 16:22:25 +08:00
    想不到啥好办法,估计只能试试启发式算法了
    Aganzo
        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 等求解器硬撸最优解
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1203 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 18:11 · PVG 02:11 · LAX 10:11 · JFK 13:11
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.