小学问题：最少要拿多少个？

manthanein

假设有一个不透明的箱子里有\(a_{1}\)个\(A_{1}\)、\(a_{2}\)个\(A_{2}\)、\(a_{3}\)个\(A_{3}\)……\(a_{n}\)个\(A_{n}\)。
我们最少要从箱子里一次性拿出多少个东西来，才能保证里面至少有\(b_{1}\)个\(A_{1}\)、\(b_{2}\)个\(A_{2}\)、\(b_{3}\)个\(A_{3}\)……\(b_{n}\)个\(A_{n}\)？
这种题目小学很多，我们来探讨一下一般的解法。

manthanein

比如说，箱子里有两种球，每种数量：
（6,8）
我们的要求：
（0,1）
可以得到结果为7。最少一次性拿出7个球，才能保证里面至少有一个第二种球。

mathe

这个考虑最不利的情况即可，就是除了一种东西差一个，其它拿光即可

manthanein

mathe 发表于 2017-5-2 20:08
这个考虑最不利的情况即可，就是除了一种东西差一个，其它拿光即可

然而不一定要求是（0,1）之类的，如果情况是（6,8），要求是（2,3）呢？

mathe

很简单，最不利是(1,8)或(6,2)，容易看出前者更差

manthanein

复杂一点的
情形：（10,8,7,1,4,3）
要求：（5,1,3,1,0,2）
又该如何计算？

manthanein

相当于已知不定方程\(\D \sum^{k}_{i=1}x_i=N\)的任何一组满足\(0 \le x_i \le a_i\)的整数解都满足\(x_i \ge b_i\)，求\(N\)的最小值。

manthanein

manthanein 发表于 2017-5-3 21:12
复杂一点的
情形：（10,8,7,1,4,3）
要求：（5,1,3,1,0,2）

（5,8,7,1,4,3） 28个
（10,1，7,1,4,3）26个
（10,8,3,1,4,3） 29个
（10,8,7,1,0,3）29个
（10,8,7,1,4,2）32个
所以至少要32个？