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

求一个凑数算法

  •  
  •   starlz · 2021-07-19 17:31:32 +08:00 · 1329 次点击
    这是一个创建于 1223 天前的主题,其中的信息可能已经有所发展或是发生改变。

    比如从 1,2,5,6,8 里边凑出 7 和 9 两位数。 前边的数不能重复使用,需要找出最优凑法。 有木有大佬提供下思路

    第 1 条附言  ·  2021-07-19 18:09:34 +08:00
    凑数就是用加法。
    最优就是尽可能的把要凑的数都凑出来,比如要凑 7 和 9,就不能用 1 和 6 先去凑 7,那样 9 就凑不出来了
    5 条回复    2021-07-19 18:32:12 +08:00
    minami
        1
    minami  
       2021-07-19 17:42:36 +08:00
    不理解凑数是什么意思,就简单理解成加法吧,用 BFS 就可以了
    misdake
        2
    misdake  
       2021-07-19 18:00:57 +08:00
    凑是指从数的集合中(不放回地)挑选一些数相加得到目标数么?
    最优凑法里的最优是指什么最优?

    问题里每个数字有三种可能状态,不使用、拿去凑 7 、拿去凑 9,要求所有凑 7 的数加一起是 7,所有凑 9 的数字加一起是 9 。
    我的话会考虑用记忆化搜索,搜索空间是[使用前 n 个数字][凑 7 还差多少][凑 9 还差多少],从[5][7][9]开始。找到[任意][0][0]就是一个解。
    xupefei
        3
    xupefei  
       2021-07-19 18:26:00 +08:00 via iPhone
    简化版背包问题
    xupefei
        4
    xupefei  
       2021-07-19 18:26:49 +08:00 via iPhone
    只能填表,没有捷径
    threebr
        5
    threebr  
       2021-07-19 18:32:12 +08:00
    可以用简单的深度搜索算法,递归深度为 m×n 。m 是[1,2,5,6,8 ]的长度,n 是[7,9]的长度。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2719 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 06:12 · PVG 14:12 · LAX 22:12 · JFK 01:12
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.