给位大佬，求个算法

显示全部楼层 · 2021-1-27 05:15:05

如果有10000个数，从1到100不等，要求按照每组100以上分组，每组数目不大于80个数，尽可能将这些数都成功分组，看看有什么方法

每组100以上是指将同一组的数加起来大于100
分 -->

千问 · 2021-1-27 05:15:05

你这需求说的并不是很清楚，当出现极端情况怎么办。
假设这10000个数，全部都是1（其实只需要1的数目超过一定数量），那你这不管怎么分，都无法满足所有要求。还有就是尽可能用更多的组还是尽可能用更少的组？
假设排除这种情况，就必须在两个条件中选择一个条件优先，例如必须魅族100以上，或者是必须不大于80个数，那这个问题就比较简单了。
我这里假设必须满足每组100以上优先，在满足这个条件的基础上再寻求每组不大于80个数，尽可能使用更少的组

importjava.util.ArrayList;
importjava.util.List;
importjava.util.Random;
publicclassTest1{
publicstaticbooleanisFull(List[I]list){
intsum=0;
for(inti:list){
sum+=i;
}
if(sum=80){
returntrue;
}
returnfalse;
}
publicstaticvoidmain(String[]args){
Randomrandom=newRandom();
int[]randomArray=newint[10000];
for(inti=0;ilist=newArrayList();
for(inti:randomArray){
booleanaddFlag=false;
for(List[I]list2:list){
if(!isFull(list2)){
list2.add(i);
addFlag=true;
break;
}
}
if(!addFlag){
List[I]list2=newArrayList[I]();
list2.add(i);
list.add(list2);
}
}
System.out.println(list.toString());
}
}

程序性能还是可以做一些优化的，不过看到一共就10000个数，优化不优化也就那么回事。
另外算法也可以做优化，可以提前预估当前数据加入后各组的变化效果，或者可以在组织间进行交换，但是这样问题就会变得更复杂了。如果要寻求那种的最优解的话，那这个问题就会太复杂。我这个做出来的只是一个尽量满足要求和性能之间的平衡，而不是求一个最优解。

千问 · 2021-1-27 05:15:05

看了楼主的题目和rumlee的分析后，我来谈谈我对这个题目的看法。挺有趣的题目，我认为不必考虑rumlee同学提出的那些疑惑，可以就认为这是未知的数组，你要做的就是判断它能否满足要求，如果不满足原因是什么，如果满足，怎么分。
1、首先考虑每组80个数（不一定每组数目一样，先考虑这个，最简单的情况）的情况。那就是125个数组。而100/80=1.25。也就是说，如果10000个数中，1的数目小于60个（60*1+20*2）=100，则怎么分都行。如果1的数目大于等于60个，那就把1分开，确保每组1的数目小于60个就可以了。但这里就可以引导出一个条件，如果1的数据量大于等于125*60个且2的数量大于等于125*20个，则怎么分都不行。
2、接下来如果需要产生每组个数小于80的组【前提提交件是1的数量小于125*60个且2的数量大于等于125*20个】，我们以70个数一组为例子。100/70取整还是1。那么如果1的数目小于40个，也是如何分都可以的。换言之就是1*x+2*y大于等于100，且x+y=80的情况中x的值。
3、分析到这里我们就可以知道，这10000个数如何分，主要就是看1,2,3,4……100每个数的数量分布。假设：优先把1,2分好。那么剩下的数保证每组不少于34个数，就肯定大于100（3*34=102）。假设把1,2,3都分配好了，那么后面的数组每组不少于25个数就肯定满足要求。

千问 · 2021-1-27 05:15:05

上面有个地方错了，应该是如果1的数据量大于等于125*60个且2的数量大于10000-1的数目-125个，则怎么分都不行。

千问 · 2021-1-27 05:15:05

感觉你的题目讲得不够严谨。不太清析。不好写算法。