注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

XYP的博客

枫染红尘谁看透

 
 
 

日志

 
 

球盒问题相关  

2016-03-12 23:27:36|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
1、盒相同,球相同,无空盒
即求出有多少种方案使m个非负整数和为n。(m个数无序)
我们把m个数从小到大排序,让a[i]>=a[i-1]。
记f[K][i][j]为用了K个数,和为i,所有数<=j的方案数。
对于选择第K+1个数,f[K+1][i][j]=f[K][i][j-1]+f[K][i-j][j]:讨论最后一个数,和为i所有数<=j可以分为:
最后一个数=j和为i-j所有数<=j的情况+最后一个数<j和为i的情况

2、盒相同,球相同,有空盒
排序后,发现若有K个为空盒,则空盒必定是在最前面的。
于是,求出无空盒的情况后,可以枚举有x个空盒,答案加上f[m][n][m-x]即可(有x个盒为空,不影响m个数总和)
即Ans=∑把n个相同的球放入m个相同的盒子的方案数=∑f[m][n][m-i]

3、盒不同,球相同,无空盒(隔板法)
分成m个盒即为 用m-1个隔板把n个球隔成m份
发现n个球前后两个之间会产生1个放隔板的空隙,n个球即为n-1个空隙。
于是问题转化为了从n-1个元素(空隙)中取出m-1个元素(隔板)的方案数。
求盒为题相关 - 1449097870 - XYP的博客
 
4、盒不同,球相同,有空盒
考虑把所有的方案中的m个盒子都放上一个球,总共放了n+m个球,显然答案不变。
于是,问题就转化成了:用(n+m-1)个球,放入m个盒中有几种方案。
答案为球盒问题相关 - 1449097870 - XYP的博客


对于球不同的问题怎么解呢?
把球编号,发现对于球相同的每一种方案,只要把n个球编号改变一下,方案就会不同。
于是,只要把球相同的情况都成上一个全排列n!就行了。
  评论这张
 
阅读(43)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018