Note de curs, probleme algoritmică, 25 octombrie 2013

În acest curs am discutat despre problema Zebughil.

Cerința

Dându-se o serie de greutăți, să se determine o modalitate de le împărți într-un număr minim de transporturi, știind că într-un transport nu pot fi duse greutăți care însumate depășesc capacitatea G.

Soluția 1

Complexitate timp: O(C_N)

Complexitate spațiu: O(1)

Se generează toate partițiile de greutăți posibile, se elimină partițiile care presupun cel puțin un transport de capacitate mai mare ca G iar dintre toate partiționările rămase se alege cea cu număr minim de transporturi.

Soluția 2

Complexitate timp: O(2^N2)

Complexitate spațiu: O(1)

Problema se rezolvă recursiv: pentru orice submulțime de greutăți se calculează numărul minim de transporturi necesare.

(1) Dacă submulțimea de greutăți nu depășește capacitatea G, atunci numărul minim de transporturi este 1.

(2) Altfel, submulțimea de greutăți se împarte în toate modurile posibile în două sub-submulțimi complementare. Pentru fiecare pereche de sub-submulțimi se calculează recursiv numărul minim de transporturi necesar pentru a transporta cele două sub-submulțimi. Dintre toate împărțirile posibile, se alege împărțirea care permite un număr minim de transporturi.

Soluția 3

Complexitate timp: O(3^N)

Complexitate spațiu: O(2^N)

Aplicând tehnica de memoizare asupra soluției 2, obținem un echilibru între complexitatea spațiu și timp.

Implementare

#include <stdio.h>

const int MAXN = 17;

int N, G;
int Blocuri[MAXN];

int SOL;

int Partitii[1 << MAXN];

int partitii(int submultime) {
	if (Partitii[submultime] == 0) {
		int i;
		int greutate = 0;
		for (i = 0; i < N; ++i) {
			if ((submultime & (1 << i)) != 0) {
				greutate += Blocuri[i];
			}
		}
		if (greutate <= G) {
			Partitii[submultime] = 1;
		} else {
			int subSubmultime;
			int complementaraSubSubmultime;
			int solutie = 0x7fffffff;
			int solutiePotentiala;
			for (subSubmultime = (submultime - 1) & submultime;
					subSubmultime > 0;
					subSubmultime = (subSubmultime - 1) & submultime) {
				complementaraSubSubmultime = subSubmultime ^ submultime;
				solutiePotentiala =
					partitii(subSubmultime) +
					partitii(complementaraSubSubmultime);
				if (solutie > solutiePotentiala) {
					solutie = solutiePotentiala;
				}
			}
			Partitii[submultime] = solutie;
		}
	}
	return Partitii[submultime];
}

int main(void) {
	int i, k;

	for (k = 0; k < 3; ++k) {
		// citirea datelor
		scanf("%d %d", &N, &G);
		for (i = 0; i < N; ++i) {
			scanf("%d", &Blocuri[i]);
		}

		// calcularea solutiei
		for (i = 0; i < (1 << N); ++i) {
			Partitii[i] = 0;
		}
		SOL = partitii((1 << N) - 1);

		// afisarea solutiei
		printf("%d\n", SOL);
	}
	return 0;
}