Pertanyaan Algoritme untuk membagi daftar menjadi beberapa grup


Saya punya daftar nama.

Saya ingin mempartisi daftar ini ke dalam kelompok dengan ukuran yang ditentukan. Semua kelompok harus sama dengan atau kurang dari ukuran yang ditentukan, dengan ukuran kelompok sejajar mungkin di seluruh kelompok, dan sedekat mungkin dengan ukuran yang ditentukan.

Algoritma apa (Java-esque pseudo code jika mungkin silakan!) Menentukan ukuran kelompok yang paling tepat?

Sebagai contoh:

Daftar berisi 13 nama - tim ukuran maksimal 3. Output (ukuran grup): 3, 3, 3, 2, 2

Daftar berisi 13 nama - tim ukuran maksimal 4. Output: 4, 3, 3, 3

Daftar berisi 31 nama - tim ukuran maksimal 5. Output: 5, 5, 5, 4, 4, 4, 4

Daftar berisi 31 nama - tim ukuran maksimal 6. Output: 6, 5, 5, 5, 5, 5

Daftar berisi 31 nama - ukuran tim maks 10. Output: 8, 8, 8, 7


4
2018-01-12 14:29


asal


Jawaban:


Ini cukup mudah. Anda menghitung hasil dari N div M dan tambahkan 1 untuk memiliki jumlah array yang benar (N adalah panjang daftar dan M ukuran tim maks), kemudian Anda iterate pada semua array untuk menambahkan item sampai Anda kehabisan item

contoh: 43 nama, jumlah tim maks 4 => 43 mod 4 + 1 = 11, tetap 3. jadi 11 array (10 dengan 4 dan 1 dengan 3)


4
2018-01-12 14:38



Saya tidak akan menulis kode untuk ini, tetapi

  1. Jika ukuran daftar merupakan kelipatan dari ukuran tim maks, bagi dengan ukuran tim untuk mendapatkan jumlah grup, semua ukuran maksimal, dan berhenti.
  2. Integer-membagi ukuran daftar dengan ukuran tim max, lalu tambahkan satu. Itu jumlah grup.
  3. Kurangi ukuran daftar dari beberapa yang lebih tinggi berikutnya; itulah jumlah tim yang kurang dari ukuran maksimal.

Ini jelas hanya bekerja untuk input yang hampir berhasil; gagal jika ukuran tim maksimal besar dibandingkan dengan ukuran daftar.


2
2018-01-12 14:36



Jika jumlah item dalam daftar itu N dan jumlah maksimal item dalam sublist adalah K, solusi dari masalah Anda berasal dari pemecahan a Persamaan Linear Diophantine

K*x + (K-1)*y = N

dengan kendala tambahan

x > 0
y >= 0

Dimana x adalah jumlah sublaman dari ukuran yang tepat K, dan y adalah jumlah sublebar panjang K-1.

EDIT: Karena koefisien untuk persamaan selalu dilepas satu dari yang lain, solusinya agak mudah:

int m = (N+K-1)/K;
int x = N - (K-1)*m; // Number of "full" lists
int y = K*M - N;     // Number of off-by-one lists

Contoh 1:

N = 31, K = 5
m = (31+5-1)/5 = 7
x = 31 - (5-1)*7 = 3 // 3 lists of 5 items
y = 5*7 - 31 = 4     // 4 lists of 4 items

Contoh 2:

N = 32, K = 4
m = (32+4-1)/4 = 8
x = 32 - (4-1)*8 = 8 // 8 lists of 4 items
y = 4*8 - 32 = 0     // no lists of 3 items

Carilah algoritme untuk menyelesaikan persamaan Diophantine linier di internet - tidak terlalu rumit, jika Anda paham Algoritma Euclidean baik. Jumlah solusi dari persamaan tanpa batasan tidak terbatas, tetapi setelah Anda menambahkan batasan, Anda harus mendapatkan solusi tunggal.


2
2018-01-12 14:42



public class Q {
public static void q(int size, int maxTeamSize) {
    int numOfTeams = size / maxTeamSize;
    int mod = size % maxTeamSize;
    numOfTeams += (mod > 0) ? 1 : 0;
    System.out.print("\n(" + size + ":" + maxTeamSize + ")");
    for (int i = 0; i < numOfTeams; i++) {
        System.out.print(" " + (size / numOfTeams + ((i < mod) ? 1 : 0)));
    }
}

public static void main(String[] args) {
    q(13, 3);
    q(12, 4);
    q(31, 5);
    q(31, 6);
}
}

0
2018-01-12 15:29