V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
tamer
V2EX  ›  问与答

回溯暴力+dp 算法求优化思路

  •  
  •   tamer · 2020-11-12 13:29:55 +08:00 · 883 次点击
    这是一个创建于 1232 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题的来源是棋牌游戏的人物的一个技能:

    严教:出牌阶段限一次,你可以选择一名其他角色。从牌堆顶亮出四张牌,该角色将这些牌分成点数之和相等的两组,你与其各获得其中一组,然后将剩余未分组的牌置入弃牌堆。若未分组的牌超过一张,你本回合手牌上限-1 。

    翻译一哈:

    给定 x 张牌,每张牌的点数都在 1-13 之间. 将 x 张牌分成点数相等的两堆,弃置多余的牌,要求弃置最少的牌.

    以下目前的思路,求指导优化方案

    仅考虑拿尽量多的牌的算法,

    如果要考虑牌本身的好坏,那么肯定还要考虑拿牌的人的技能,场上的局势等等才行

    所以如果只是给予酒,桃,高收益锦囊,等等这样的牌高权重其实并不合理

    最开始想到是暴力回溯:

    每张牌都有三种状态:给第一个人,给第二个人,弃置

    直接一个熟悉的回溯,算法复杂度高达 3 的 N 次方,这也是想优化的直接原因

    其次还有个重复问题没有解决,

    考虑点数 A,2,3,4 的情况,

    第一个人拿 A,4,第二个人拿 2,3,

    第一人拿 2,3,第二个人拿 A,4

    这两个完全是重复解,但没有想到好的去重方案

    印象中,去重还可以顺带达到剪枝效果。

    然后就是优化方案,目前也没有想到时间复杂度比较好的方案

    定义数组 dp, dp.i 表示 bag1 中的元素和-bag2 元素和==i 的所有可能组合,

    遍历到第 n 张牌时, 更新当前 dp 数组

    dp[0+n] += 第 n 张牌分别放入 dp[0]中的 bag1 产生的新的组合
    do[1+n] += 第 n 张牌分别放入 dp[1]中的 bag1 产生的新的组合
    //然后更新将其放入 bag2 中的组合
    
    

    最后 dp0 即为解

    时间复杂度不知道怎么怎么算,想知道有没有更好的解决思路. 因为跟背包问题看起来类似,所以强行套了 dp

    2 条回复    2020-11-16 09:56:33 +08:00
    guchengyehai1
        1
    guchengyehai1  
       2020-11-12 21:55:00 +08:00 via Android
    动态规划博弈问题?
    tamer
        2
    tamer  
    OP
       2020-11-16 09:56:33 +08:00
    @guchengyehai1 老哥我的问题,请移步
    https://v2ex.com/t/725628

    简化了描述
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   958 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 21:13 · PVG 05:13 · LAX 14:13 · JFK 17:13
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.