Алгоритм разбиения массива из N элементов на K частей, где разница между суммами элементов минимальна

Question

Мне нужно написать алгоритм для оптимального разделения массива из N элементов на K частей, где разница между суммами элементов в каждой части минимальна (где все части максимально эквивалентны друг другу). Порядок элементов в массиве нельзя менять. Мне нужно найти индексы массива, которые приведут к оптимальному разделу.

Я видел похожие проблемы, опубликованные здесь, но ни одна из них не была настолько абстрактной и сложной. В настоящее время я беру класс алгоритмов C ++, но он предназначен для личного / побочного проекта, а не для какого-либо назначения.

Вот очень грубый стартовый код, который пытается использовать рекурсию для разделения массива и даже разделов, но результат далек от оптимального, и я даже не уверен, что нахожусь на правильном пути. Я предполагаю, что где-то есть гораздо лучший алгоритм. Приветствуются любые указания.

#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;
   } 
}```