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

一道看着简单的题,但是不知道怎么求解,各位大佬来思考下

  •  1
     
  •   yarns · 2021-09-09 17:56:21 +08:00 · 954 次点击
    这是一个创建于 932 天前的主题,其中的信息可能已经有所发展或是发生改变。

    现有如下问题:

    需要总量为 300 个的水果

    且满足苹果 100 个 橘子 100 个 桃子 100 个

    目前要从 10 家单位中随机选取 3 家 且每家单位拿取总数(苹果+橘子+桃子)100 个

    假设目前数据如下,请给出最优算法

    单位名称 苹果 橘子 桃子
    A 40 50 60
    B 50 50 50
    C 50 50 0
    D 100 0 100
    E 80 20 40
    F 40 50 10
    G 10 50 30
    H 20 20 30
    I 80 90 10
    J 60 20 10
    8 条回复    2021-09-22 10:19:46 +08:00
    yarns
        1
    yarns  
    OP
       2021-09-09 18:21:54 +08:00
    目前两个解
    1 、硬算 会出现几个单位 n 的阶乘种排序导致的结果 计算次数贼大
    2 、常量特征 设置一个特征值 比如 50 根据 n 单位的苹果和橘子和桃子的差值和平均值 得出特征值 值越小越能组合成 100 按特征值来整
    wlsnx
        2
    wlsnx  
       2021-09-10 11:36:48 +08:00
    这怎么随机?题目是要求找出符合条件的一个解吧。
    先排序,把 1 (最大)+2 最小>100 和 1 (最小)+2 最大<100 的去掉,肯定不满足条件。
    然后暴力破解,假设取出先 A,把苹果>60 或橘子>50 或桃子>40 的去掉,再从剩余结果中取一个,去掉不符合条件的再取第三个,如果剩余结果为空就回溯。
    yarns
        3
    yarns  
    OP
       2021-09-14 19:21:35 +08:00
    @wlsnx 目前就是这样的硬算 一旦变量从 1w 家单位中选取 100 家 直接 gg
    yarns
        5
    yarns  
    OP
       2021-09-17 10:23:49 +08:00
    @wlsnx 3 sum 只能解决横向之和吧 纵向和还是只能瞎猜
    wlsnx
        6
    wlsnx  
       2021-09-17 10:51:51 +08:00
    你这个问题就是一个 k 数之和问题,简化一下就是在某一列做 k 数之和,再验证其他列是否也都正好合适。k 为 3 时很简单,k 为 100 时基本无解。
    yarns
        7
    yarns  
    OP
       2021-09-22 10:19:07 +08:00
    @wlsnx 没法了 就用硬算了 用差值来解决了 横向之和用比例 然后算纵向之和与 100 的差值是多少 然后遍历行来补差值
    yarns
        8
    yarns  
    OP
       2021-09-22 10:19:46 +08:00
    @wlsnx
    name passenger cargo auto temp_sum p_count c_count a_count
    0 A 40 50 60 150 27.0 33.0 40.0
    1 B 50 50 50 150 33.0 33.0 34.0
    2 F 40 50 10 100 40.0 50.0 10.0
    差值分别为------- 0.0 : -16.0 : 16.0
    耗时: 0.011885099999999982 秒
    {'name': 'A', 'passenger': 27.0, 'cargo': 17.0, 'auto': 56.0}
    {'name': 'B', 'passenger': 33.0, 'cargo': 33.0, 'auto': 34.0}
    {'name': 'F', 'passenger': 40.0, 'cargo': 50.0, 'auto': 10.0}
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2669 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 15:27 · PVG 23:27 · LAX 08:27 · JFK 11:27
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.