Chinaunix首页 | 论坛 | 博客
  • 博客访问: 157260
  • 博文数量: 33
  • 博客积分: 2057
  • 博客等级: 大尉
  • 技术积分: 430
  • 用 户 组: 普通用户
  • 注册时间: 2007-11-19 16:37
文章分类
文章存档

2013年(2)

2012年(23)

2011年(8)

分类: Python/Ruby

2011-10-06 23:29:29

正在愁着找工作,偶尔在网上看到csdn的一个讨论东软面试题的帖子。不知什么原因,在那儿无法回复帖子,所以就把话说到这里来吧。

题目的意思是: 有若干物品 w1,w2,w3...,装进一个背包,需要装入重量恰好w,用递归算法,语言不限。
一些人贴出了代码,有java的,有c的,但没有人讲一下他的代码的思路。  我这里把大概思路说一下:

这个问题涉及到组合combination.   关于组合和排列(permutation), 都有很经典的算法(好像在大学数据结构上不学,我是在chinaunix的python论坛上看到的,我本科学的不是计算机)。

组合:combination(ws)
如果只有一个元素,则将它返回 return ws[0]
否则(多个元素),返回除第一个元素外剩余所有元素的每个组合,以及这每个组合加上这第一个元素

return   [ comb  for comb in combination(ws-ws[0])] +
              [ ws[0] +comb for comb in combination(ws-ws[0])]


排列:permutation(ws)
如果只有一个元素,则将它返回 return ws[0]
否则(多个元素),返回 每个元素外剩余所有元素的每个排列,以及这每个排列加上这个元素

return  [perm  for i in ws  for perm in permutation(ws-ws[i])] +
             [ ws[i]+perm  for i in ws  for perm in permutation(ws-ws[i])]

可以看到,组合和排列的算法有点类似。当然这个题目用的是组合,不是排列。
那么,我们只要在组合算法中加入一个检查: check(comb)是否等于w; 等于则跳出,不等于则继续生成comb。所以,这个问题主要在于生成组合,而生成组合的算法本身是递归的。
事实上,不递归的组合我还不会弄呢 ^-^。
阅读(3164) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~