贴邮票难题

medie2005

ls搞错了吧.x+2y+3z=85500 的整数解不含x=y=0, z=85500/3这个情形.

gxqcn

那这样好了，令 $x=y=1, z=(85500-3)//3$ 总可以了吧， 此时9999封本市信仍无法正好帖邮票。 不过，x、y、z 只要为非负整数就可以了， 不知 ls 为什么说不包含我列举的这组解？

mathe

还是用计算机穷举吧，问题复杂度不大。 主要是同一种买法可以有多种不同的贴法。如果是计算多少种贴法，直接用数学方法应该比较简单；不过换成多少种买法应该复杂些

medie2005

northwolves的答案是对的. 考虑x+2y=k的解个数.显然是int(k/2.0)+1. 然后,再对k求和.

northwolves

原帖由 gxqcn 于 2008-12-31 07:46 发表 既不是无心人的那般多，也不是 northwolves 给的那么多。 比如若 $x=y=0, z=85500//3$，则本市信封无法恰好帖上所需邮资的邮票。

有道理,考虑不周

northwolves

原帖由 mathe 于 2008-12-31 08:56 发表 还是用计算机穷举吧，问题复杂度不大。 主要是同一种买法可以有多种不同的贴法。如果是计算多少种贴法，直接用数学方法应该比较简单；不过换成多少种买法应该复杂些

楼主的问题没有问贴法有多少种.

medie2005

xxxxx [ 本帖最后由 medie2005 于 2008-12-31 09:36 编辑 ]

northwolves

应该分三种情况: x+2y+3z=85500 1. z=0---->85500\2+1 种方法 2. 0x+2y=85500-3z 3. 7584*2x+2y=85500-3z 且x>=(z-7584*2)

shshsh_0510

过年好 这个感觉不难，只是有点繁，用计算机解很简单。 先求简单一点的：3种信分别1.2,1.6,2.4,分为a,b,c封。用0.4,0.8的邮票，同样的问题。 对这个，0.8的张数x属于 [0，a+2b+3c] 于是f(a,b,c)=a+2b+3c 对于原题： 设1.2张数x,对于每个x将产生若干的(a,b,c)组合。其中可能有某些 f(a1,b1,c1)=f(a2,b2,c2),要排除。 设x中 两个1.2贴同一封，一个1.2贴一封外地，一个1.2贴一封本地 这3种分别为 i,j,k 则 对应的a,b,c 为：a=j ,b=9999-k,c=7548-i-j k属于[0,x] 对于给定的k, i属于[0,int((x-k)/2)] j=x-i-k f(a,b,c)=a+2b+3c=j+2*(9999-k)+3(7548-i-j)=2*9999+3*7548-2x-i i相等则f(a,b,c)，既i的取值决定f()的类数 只需再讨论i的取值

shshsh_0510

当7548+9999>x>2*7548时 i属于[0,7548] 当x>7548+9999时 i属于[x-7548-9999,7548] 当x<2*7548时 i属于[0,int(x/2)] 然后用程序对x求和