一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1056|回复: 11
收起左侧

[算法题] 给一堆牌,求出最接近21点的组合 (blackjack)

[复制链接] |试试Instant~ |关注本帖
traceroute_su 发表于 2014-10-12 18:28:39 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
最近在准备面试,遇到这样一道题,除了brute force,没有什么好的办法。
举例:
2,3,4,5,J,K
最好的组合应该是 2,4,5, J 和2, 4, 5, K
我brute force就是two sum一直到5sum(因为blackjack最多5张牌)。但是拿到最接近的组合需要check所有combination,我真心没想到啥好办法解决。
面试的时候我不能连写几个求sum的函数,感觉不靠谱。
希望大家指导下我,给我一些思路。谢谢
372284362 发表于 2014-10-12 18:47:30 | 显示全部楼层
正常来说用dfs-id深搜应该可以吧!
回复 支持 反对

使用道具 举报

372284362 发表于 2014-10-12 18:48:32 | 显示全部楼层
暴力算法也行,因为最多也就2^5=32中情况么!
回复 支持 反对

使用道具 举报

 楼主| traceroute_su 发表于 2014-10-12 19:04:51 | 显示全部楼层
372284362 发表于 2014-10-12 18:48
暴力算法也行,因为最多也就2^5=32中情况么!

不是O(n^5)么?
回复 支持 反对

使用道具 举报

372284362 发表于 2014-10-12 19:34:07 | 显示全部楼层

题目要求是给定五张牌吗?还是给定一副扑克?

如果是给定五张牌的话肯定就32种情况呗!要是任意一副扑克或者给定一堆不一定几张牌的话还是深搜吧。。。
回复 支持 反对

使用道具 举报

1guangnian 发表于 2014-10-12 22:15:50 | 显示全部楼层
dp[i][j][k], 前i张牌,选j张,和为k是否可行,最后看可行方案中离21最近的k就好了
回复 支持 反对

使用道具 举报

1guangnian 发表于 2014-10-12 22:17:36 | 显示全部楼层
k最大就41就行了吧
回复 支持 反对

使用道具 举报

 楼主| traceroute_su 发表于 2014-10-13 06:16:55 | 显示全部楼层
本帖最后由 traceroute_su 于 2014-10-13 06:27 编辑
1guangnian 发表于 2014-10-12 22:17
k最大就41就行了吧

hi 校友 感觉这是subset sum问题 但是与subset不同的是这里限制了牌数 你说那个思路 能不能告诉我dp转移方程啊
回复 支持 反对

使用道具 举报

1guangnian 发表于 2014-10-13 06:26:45 | 显示全部楼层
traceroute_su 发表于 2014-10-13 06:16
hi 校友 感觉这是subset sum问题 dp应该差不多 k最大21吧。。。 而且我感觉dp数组 二维是不是就够了 dp[j ...

哦。。我是想,可能有的牌点数大于21这种。。不过好像不太可能。。。4 sum的话,首先你要记录方案数啊,其次,一个数的范围可能很大,你的memory不够
回复 支持 反对

使用道具 举报

1guangnian 发表于 2014-10-13 06:28:09 | 显示全部楼层
traceroute_su 发表于 2014-10-13 06:16
hi 校友 感觉这是subset sum问题 dp应该差不多 k最大21吧。。。 而且我感觉dp数组 二维是不是就够了 dp[j ...

嗯。。是的,牌的点数都大于等于0的话,dp顺序注意下就可以了
回复 支持 反对

使用道具 举报

1guangnian 发表于 2014-10-13 06:32:48 | 显示全部楼层
traceroute_su 发表于 2014-10-13 06:16
hi 校友 感觉这是subset sum问题 但是与subset不同的是这里限制了牌数 你说那个思路 能不能告诉我dp转移 ...

dp[j][k] -> dp[i+1][j][k],这个表示不选第i+1张牌
dp[j][k] -> dp[i+1][j+1][k+a[i+1]], 这个表示要选第i+1张牌,这里判断下k+a[i+1]是不是超出范围
base:dp[0][0][0] = true,注意我的牌的下标从1开始
回复 支持 反对

使用道具 举报

 楼主| traceroute_su 发表于 2014-10-13 07:03:52 | 显示全部楼层
1guangnian 发表于 2014-10-13 06:32
dp[j][k] -> dp[j][k],这个表示不选第i+1张牌
dp[j][k] -> dp[j+1][k+a], 这个表示要选第i+1张牌,这里 ...

收到!能明白你的意思。
我刚才想明白为什么ksum不能用subset sum的办法写 是因为target不定。如果target不定,本质是背包问题的subset sum就是NPC问题。所以用了排序移动指针的办法是最快。但是这里和就是21,常数级别,用dp完全没问题。谢谢校友解惑。非常感谢
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 15:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表