INFOMAN брой 18

#include <stdio.h>
#include <values.h>
#define MAX 100
#define max(a,b) ((a > b)?a :b) //Връща по - големия аргумент

int s[MAX] = { 0,23,15,89,170,25,1,86,80,2,27 }; // Редица ( първият не се ползва )
unsigned n = 10; // Брой елементи в редицата
unsigned k =4; //Брой групи
long p[MAX]; // Префиксни суми
long f[MAX][MAX]; // Целева функция
long b[MAX][MAX]; // За възстановяване на решението

long DoPartition(unsigned k) { // Извършва оптимално разделяне на k групи
int i,j,l;
	// Пресмятаме префиксните суми 
	p[0] = 0;
	for (i=1; i<=n; i++)
		p[i] = p[i-1] + s[i];

	// Установяване на граничните условия
	for (i=1; i<=n; i++) f[i][1] = p[i];
	for (i=1; i<=k; i++) f[1][j] = s[1];

	// Основен цикъл
	for (i=2; i<=n; i++)
		for (j=2; j<=k; j++) {
			f[i][j] = MAXINT;
			for (l=1; l<=i-1; l++) {
				int m = max(f[l][j-1],p[i]-p[l]);
				if (f[i][j] > m) {
					f[i][j] = m;
					b[i][j] = l;
				}
			}
		}
	return f[n][k];
}

void Print(unsigned from, unsigned to) {
	printf("\n");
	for (int i=from; i<=to; i++)
	printf("%d ",s[i]);
}

void PrintPartition(unsigned n, unsigned k) {
	if (k == 1)
		Print(1,n);
	else {
		PrintPartition(b[n][k],k-1);
		Print(b[n][k]+1,n);
	}
}

int main() {
	printf("\n Максимална сума в някоя от групите : %ld",DoPartition(k));
	PrintPartition(n,k);
	return 0;
}