这是一个创建于 1476 天前的主题，其中的信息可能已经有所发展或是发生改变。
题的来源是棋牌游戏的人物的一个技能:
严教：出牌阶段限一次，你可以选择一名其他角色。从牌堆顶亮出四张牌，该角色将这些牌分成点数之和相等的两组，你与其各获得其中一组，然后将剩余未分组的牌置入弃牌堆。若未分组的牌超过一张，你本回合手牌上限-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
 |
1
guchengyehai1 2020-11-12 21:55:00 +08:00 via Android
动态规划博弈问题？
|
 |
2
tamer OP |
Select Language