求证一个数学模型

jihuyao

Puzzled for a few weeks and finally realized this is a similar problem many may have already known, that is, distribute students in n schools to m testing sites as evenly as possible.  To make it short, in case 1 choose 2 smallest groups (2,3) and place in 2 box’s and result is 3.  In case 2, choose 5 smallest groups and place in 3 boxes like {10,5,3+2+2} or {10,5+2,3+2} or whatever equivalent, then result is 10.

newkid

jihuyao 发表于 2019-7-26 23:27
Puzzled for a few weeks and finally realized this is a similar problem many may have already known,  ...

你这个所谓的smallest groups的个数是怎么确定的？比如第一个例子，为什么选两个一组？第二个例子总共7个框，为什么选5个一组？

我很好奇楼上是怎么找到这贴的？通过搜索引擎？

jihuyao

just happened to check some recent posts and saw it.  The whole problem is more complicated than the present two examples.  Take the 2nd collection {16,14,5,4,3,,2,2} as example, if m=6 then choose only 2 smallest groups {2,2}.  Once they are completely picked the process ends.  So one can pick in the same way as in PS1 and this way is always correct as long as n-m=m-1.  That is why the picks in case 1 works but it does not work in case 2.  And that is why I was confused.  The key point is whenever only m-1 groups are available the pick process stops.  In other words, in each pick, one needs to consume n-(m-1) groups as much as possible individually and collectively.  Maybe there is extreme situation existing but the n1<=n2..... constraints may prevent it from happening.  Or at least one can evaluate the extreme situation in the two ways mentioned above.  

newkid

这个题目很有意思，最近我花了点时间思考，得出一个结论，希望有人予以验证或反驳。


题目的要求是通过最少的次数达到一种状态，使得无法再取M个球。这就说明剩下的筐里，最多只能M-1筐还有球，其他全部为空。最后剩球的这M-1个筐，就是按初始值排序，最大的M-1个筐（以下称为保留筐）。

把所有筐从大到小排序。假定第M个筐里面球个数为K。

把最大的M-1个保留筐放一边，假设剩下其他筐的球总数为P。

则最小次数=GREATEST(K,CEIL(P/M))

上述例子中，M=3, 排序后{16,12,10,5,3,2,2}

此时第M个筐里面有10个，K=10

保留筐为最大的两个，剩下5个，此时P=10+5+3+2+2=22

最小次数=GREATEST(10,CEIL(22/3))=10
取球规则：
当总筐数 <= M-1+M, 则每次都从当前最小的M个筐取球，也就是楼主的做法。
当总筐数 > M-1+M, 先把最大的M-1个保留筐放一边，剩下的每次从当前最大的M个筐取球，直到取不出。然后再加入保留筐，改成从当前最小的M个筐取球，直到取不出就结束。

以题目为例：{16,12,10,5,3,2,2}先把保留筐{16,12}放一边，然后永远取最大的三个筐：
{16,12,9,4,2,2,2}
{16,12,8,3,1,2,2}
{16,12,7,2,1,1,2}
{16,12,6,1,1,1,1}
{16,12,5,0,0,1,1}
{16,12,4,0,0,0,0} ----- 到这一步再也取不出了，此时把保留筐加入，取最小的三个筐
{15,11,3,0,0,0,0}
{14,10,2,0,0,0,0}
{13,9,1,0,0,0,0}
{12,8,0,0,0,0,0} ----- 至此结束，总共十次

jihuyao

I was wondering my post delay and now see it.  But I skipped answering why choosing the smallest groups so let me add it here.  Assuming someone does not choose smallest groups and find out the minimum number to complete the process.  Also say group j is chosen rather than group i and here Ni<Nj.  In this case among those minimum pickup, if it contains j then j can be fully replaced by i.  After that there is still some j left which are picked up together with Km.  If all these Km are not in those chosen groups these picks are not needed.  So pick Ni can achieve the minimum number at least like picking Nj.  As to how to operate picking process, my feeling is once the smallest groups are chosen, for each time picking, pick up the group with the max count (this max is dynamically changing).  There may be one situation, say one chosen group has much more than other chosen groups.  In this case  one can pick that group every time untiil the process stops.  Which means one may add up other groups for pick 2,3,etc every time (from 2nd largest to smallest chosen groups).  By constraint Ni<=Nj, I would think the combination every time can not have duplicated Nk picked.  I did not play with this way but do not see any flaw in it.  In other cases, one may play like this,  say based on the total number of all chosen groups divided by number to be picked every time, this calculated average number may be at least equal to Nmax+part of N2ndmax+moreNx???.  So add up each 2nd, 3rd, etc pick up to the calculated average with those chosen groups in order by count desc (large to small).  I never played this way so I could be wrong.  But I feel it is impossible to got duplicate pick for any chosen group in this way.  Last thing is what about any unchosen groups which needed for compensation when needed?  Will they provide enough compensation in extreme situation.  I have to stop here for all the scenarios.  Simply too much to think about.

newkid

这个论坛把北京时间凌晨发的贴自动归入审核，要人工放出来。所以如果你在海外发帖就可能遇到这种情况。但是我现在有了审核权，有时候就可以提早放出来。

在你的论述中，“In this case among those minimum pickup, if it contains j then j can be fully replaced by i”这个结论是不成立的。你的这个取法会让数量少的筐提早取完，这有时候对总次数有利，有时候不是。

我们以一个简化的例子来说明。假设开始状态{4,3,2,1}，要求M=2，每次取两筐。

按照我的做法，把M-1作为保留筐，M-1=1，最终剩下一个保留筐，即最大值4那个筐是保留筐。其他三个{3,2,1}, 此时非保留筐数=3, 而3>M, 我们的策略不是要让这三个筐尽早结束，恰恰相反，要尽可能地取干净，最后才不会动用到保留筐里面的球。所以这时候要采取取最大的策略而不是取最小，取最大会让数字越来越平均，最后剩余最少。

取最小策略：{3,2,1}=>{3,1,0}=>{2,0,0} 两次就变成不可取状态。最终需要从保留筐{4}里面取球来帮助消化。
取最大策略：{3,2,1}=>{2,1,1}=>{1,0,1}=>{0,0,0} 三次才变成不可取状态，但是它不需要动用保留筐！

保留筐里面剩的球越多，总次数就越少。

你的论述有些地方让人看不懂，对一些术语应该先有清晰的定义，比如Km是什么意思？group又是指什么？每当你想到一种situation, 就应该举个例子说明，这样别人才能跟得上思路。

liuzhe_521

newkid 发表于 2021-2-4 01:12
这个题目很有意思，最近我花了点时间思考，得出一个结论，希望有人予以验证或反驳。题目的要求是通过最少的 ...

看起来是对的，要排除掉最大的两个保留筐，后面要计算的就是：最少取多少次可以将剩余筐小球尽量取完。
但为什么是CEIL(P/M) 这个公式？  有哪些定理、依据，怎么证明呢？
我试了几种场景，没找到反例。

newkid

liuzhe_521 发表于 2023-5-7 02:27
看起来是对的，要排除掉最大的两个保留筐，后面要计算的就是：最少取多少次可以将剩余筐小球尽量取完。但为 ...

又是两年过去了，楼主还记得这个贴，真是奇迹！
那个公式是我总结的，并没有什么定理可以证明。等我有空回以起来解释一下。

newkid

liuzhe_521 发表于 2023-5-7 02:27
看起来是对的，要排除掉最大的两个保留筐，后面要计算的就是：最少取多少次可以将剩余筐小球尽量取完。但为 ...

这个 ceil(p/m) 是很容易理解的。上面的规则有一句话：
把最大的M-1个保留筐放一边，假设剩下其他筐的球总数为P。

剩下的 p 个肯定要取到完，所以总次数至少为ceil(p/m)。

把P个全取完之后，有可能那些"保留筐"里面还有，还得继续，所以另外还有个K, 这两个取较大的一个才是真正取完的次数。

liuzhe_521

newkid 发表于 2023-5-10 22:24
这个 ceil(p/m) 是很容易理解的。上面的规则有一句话：把最大的M-1个保留筐放一边，假设剩下其他筐的球总数 ...

这个题目最开始来自于福袋商品（组合商品）库存计算的问题。福袋内有m种商品，每个商品都有自己的库存量，一个福袋的商品随机搭配，问题是：福袋的库存如何计算？为避免超卖，需要给出一个最小库存量做为上架数量。

目前看来是已经有解了，感谢newkid，感谢各位回复的水友们，几年过去了，有点物是人非的感觉。。。