goat2.cpp

#include <iostream>
using namespace std;
void InsertionSort(unsigned* arr, int n)
{
	int i, j,key;
	for (i = 1; i < n; i++)
	{
		j = i - 1;
		key = arr[i];
		while (j >= 0 && key > arr[j])
		{
			arr[j + 1] = arr[j];
			j = j - 1;
		}
		arr[j + 1] = key;
	}
}

int main()
{
	unsigned n = 0, k = 0;
	cout << "Enter number of goat N and then K courses: " << endl;
	cin >> n >> k;
	unsigned* weights = new(nothrow) unsigned[n];
	if (!weights)
	{
		cout << "Error allocating memory..." << endl;
		return -1;
	}
	cout << "Enter weight of every goat respectively: " << endl;
	for (int i = 0; i < n; i++)
	{
		cout << "Goat[" << i + 1 << "] : " << endl;
		cin >> weights[i];
	}
	InsertionSort(weights, n);
	
	int currMinCapacity = weights[0], end = n - 1, curr = 0, tempCourses = k;
	
	int min = weights[0];
	min += weights[end];
	currMinCapacity += weights[end];
	bool attempted = false;

	for (int i = 0; i < n; i++)
	{
		if (min < currMinCapacity)
			min = currMinCapacity;
		if (tempCourses == 0)
		{
			currMinCapacity += weights[end];
			tempCourses = k;
		}
		
		int j = i;
		
		while(tempCourses > 0 && j <= end)
		{
			int temp = curr;
			curr += weights[j];
			if (curr == currMinCapacity)
			{
				attempted = true;
				end--;
				curr = 0;
				tempCourses--;
				break;
			}

			if (curr > currMinCapacity)
			{
				curr = temp;
				attempted = true;
			}
			j++;
			if (j > end)
				tempCourses--;
		}
	}
	cout << "Min Capacity: " << min << endl;
	delete[] weights;

	system("PAUSE");
}