如果有10000個數，從1到100不等，要求按照每組100以上分組，每組數目不大于80個數，盡可能將這些數都成功分組，看看有什么方法
每組100以上是指將同一組的數加起來大于100
uj5u.com熱心網友回復：
你這需求說的并不是很清楚，當出現極端情況怎么辦。假設這10000個數，全部都是1（其實只需要1的數目超過一定數量），那你這不管怎么分，都無法滿足所有要求。還有就是盡可能用更多的組還是盡可能用更少的組？
假設排除這種情況，就必須在兩個條件中選擇一個條件優先，例如必須魅族100以上，或者是必須不大于80個數，那這個問題就比較簡單了。
我這里假設必須滿足每組100以上優先，在滿足這個條件的基礎上再尋求每組不大于80個數，盡可能使用更少的組
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class Test1 {
public static boolean isFull(List<Integer> list) {
int sum = 0;
for (int i : list) {
sum += i;
}
if (sum < 100) {
return false;
}
if (list.size() >= 80) {
return true;
}
return false;
}
public static void main(String[] args) {
Random random = new Random();
int[] randomArray = new int[10000];
for (int i = 0; i < randomArray.length; i++) {
randomArray[i] = random.nextInt(100) + 1;
}
List<List<Integer>> list = new ArrayList<List<Integer>>();
for (int i : randomArray) {
boolean addFlag = false;
for (List<Integer> list2 : list) {
if (!isFull(list2)) {
list2.add(i);
addFlag = true;
break;
}
}
if (!addFlag) {
List<Integer> list2 = new ArrayList<Integer>();
list2.add(i);
list.add(list2);
}
}
System.out.println(list.toString());
}
}
程式性能還是可以做一些優化的，不過看到一共就10000個數，優化不優化也就那么回事。
另外演算法也可以做優化，可以提前預估當前資料加入后各組的變化效果，或者可以在組織間進行交換，但是這樣問題就會變得更復雜了。如果要尋求那種的最優解的話，那這個問題就會太復雜。我這個做出來的只是一個盡量滿足要求和性能之間的平衡，而不是求一個最優解。
uj5u.com熱心網友回復：
看了樓主的題目和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個數就肯定滿足要求。
uj5u.com熱心網友回復：
上面有個地方錯了，應該是如果1的資料量大于等于125*60個且2的數量大于10000-1的數目-125個，則怎么分都不行。轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/8299.html
標籤：Java EE
上一篇：RSA公鑰私鑰