Algorithm to partition an array of N elements into K parts where the difference between the sums of elements is minimal

Viewed 291

I need to write an algorithm to optimally partition an array of N elements into K parts where the difference between the sums of the elements in each part is minimal (where all of the parts are as equivalent to one another as possible). The order of elements in the array must not be reordered. I need to find the array indices that will result in the optimal partition.

I have seen similar problems posted here, but none quite as abstract and complicated. I am currently taking a C++ algorithms class, but this is for a personal/side project, not any sort of assignment.

Here's some very rough starter code that attempts to use recursion to partition the array and even out the partitions, but the result is far from optimal, and I'm not even sure I'm on the right track. I'm guessing there's a far better algorithm out there somewhere. Any guidance would be appreciated.

#include <iostream>
#include <fstream>
#include <vector>
#include <limits>
using namespace std;

void books(ifstream&);
void calculate(vector<int>&, vector<string>&, int, int, int, int, bool&, int&);


int main(int argc, const char * argv[]) {
   vector<int> list;
   vector<string> days;
   int num;
   
   ifstream fin("list.txt");
   while(fin >> num) {
       list.push_back(num);
   }
   fin.close();
   
   int wordsPerBook = 0;
   for (auto i : list) {
       wordsPerBook += i;
       cout << i << " ";
   }
   cout << endl;
   
   int numDays = 8;
   int wordsPerDay = wordsPerBook / numDays;
   cout << "wordsPerBook: " << wordsPerBook << endl;
   cout << "wordsPerDay: " << wordsPerDay << endl << endl;
   
   int start = 0, day = 1;
   int minOverPlus1Error = INT_MAX;
   bool extraDay = false;
   calculate(list, days, start, day, numDays, wordsPerDay, extraDay, minOverPlus1Error);
   
   cout << endl << "Days: " << endl;
   for (auto i : days)
       cout << i << endl;
   cout << endl;
   
   if (extraDay && day == 1) {
       extraDay = false;
       cout << endl << "*********************Re-Calculate*********************" << endl;
       days.clear();
       days.shrink_to_fit();
       calculate(list, days, 0, day, numDays, wordsPerDay, extraDay, minOverPlus1Error);
   }
   
   cout << endl << "Days: " << endl;
   for (auto i : days)
       cout << i << endl;
   cout << endl;
   
   if (extraDay && day == 1) {
       extraDay = false;
       cout << endl << "*********************Re-Calculate*********************" << endl;
       days.clear();
       days.shrink_to_fit();
       calculate(list, days, 0, day, numDays, wordsPerDay, extraDay, minOverPlus1Error);
   }
   
   cout << endl << "Days: " << endl;
   for (auto i : days)
       cout << i << endl;
   cout << endl;
   
   return 0;
}

void calculate(vector<int>& list, vector<string>& days, int start, int day, int numDays, int wordsPerDay, bool& extraDay, int& minOverPlus1Error) {
   int sumUnder = 0, sumOver = 0, sumUnderMinus1 = 0, sumOverPlus1 = 0;
   int nextStart = 0, words = 0;
   
   cout << "day: " << day << endl;
   if (day > numDays) {
       extraDay = true;
       return;
   }
   
   if (start >= list.size() - 1)
       return;
   
   for (int i = start; i < list.size() - 1; i++) {
       if (sumOver < wordsPerDay) {
           cout << list[i] << " ";
           sumUnder += list[i];
           
           if (i + 1 < list.size())
               sumOver = sumUnder + list[i + 1];
           else
               sumOver = sumUnder;
           
           if (i - 1 >= 0)
               sumUnderMinus1 = sumUnder - list[i - 1];
           else
               sumUnderMinus1 = sumUnder;
           
           if (i + 2 < list.size())
               sumOverPlus1 = sumOver + list[i + 2];
           else
               sumOverPlus1 = sumOver;
           
           nextStart = i + 1;
       
       }
       if (minOverPlus1Error == sumOverPlus1 - wordsPerDay) {
           sumOver = sumOverPlus1;
           sumOverPlus1 = sumOverPlus1 + list[i + 3];
       }
       else if (minOverPlus1Error == sumOverPlus1 + list[i + 3] - wordsPerDay) {
           sumOver = sumOverPlus1 + list[i + 3];
           sumOverPlus1 = sumOverPlus1 + list[i + 3] + list[i + 4];
       }
       
   }
   
   if (minOverPlus1Error == sumOver - wordsPerDay) {
       cout << list[nextStart] << " ";
       nextStart += 1;
       cout << list[nextStart] << " ";
       nextStart += 1;
       cout << list[nextStart] << " ";
       nextStart += 1;
       words = sumOver;
       minOverPlus1Error = INT_MAX;
   }
   else if (minOverPlus1Error == sumOver - wordsPerDay) {
       cout << list[nextStart] << " ";
       nextStart += 1;
       cout << list[nextStart] << " ";
       nextStart += 1;
       cout << list[nextStart] << " ";
       nextStart += 1;
       cout << list[nextStart] << " ";
       nextStart += 1;
       words = sumOver;
       minOverPlus1Error = INT_MAX;
   }
   else if ((wordsPerDay - sumUnder) > (sumOver - wordsPerDay)) {
       cout << list[nextStart] << " ";
       nextStart += 1;
       words = sumOver;
   }
   else
       words = sumUnder;

       
   days.push_back("Day " + to_string(day) + ": Chs " + to_string(start + 1) + "-" + to_string(nextStart) + " Words: " + to_string(words));
   cout << endl << "nextStart: " << nextStart << endl;
   cout << "sumUnder: " << sumUnder << " error: " << wordsPerDay - sumUnder << endl;
   cout << "sumOver: " << sumOver << " error: " << sumOver - wordsPerDay << endl;
   cout << "sumUnderMinus1: " << sumUnderMinus1 << " error: " << wordsPerDay - sumUnderMinus1 << endl;
   cout << "sumOverPlus1: " << sumOverPlus1 << " error: " << sumOverPlus1 - wordsPerDay << endl << endl;
       
   calculate(list, days, nextStart, day + 1, numDays, wordsPerDay, extraDay, minOverPlus1Error);
   
   if (extraDay && minOverPlus1Error > sumOverPlus1 - wordsPerDay) {
       minOverPlus1Error = sumOverPlus1 - wordsPerDay;
       cout << "minOverPlus1Error: " << minOverPlus1Error << endl;
   } 
}```
0 Answers
Related