Алгоритм деления списка чисел и суммирования> = X миллионов

Question

У меня есть 9 чисел, которые я хочу разделить на два списка, и оба списка должны составить определенную сумму при суммировании.Например, у меня есть список int s:

List<int> test = new List<int>
{
    1963000, 1963000, 393000, 86000,
    393000, 393000, 176000, 420000,
    3193000
};

И я хочу иметь 2 списка чисел, которые, когда вы их суммируете, достигают 4 миллионов.

Неважно, если два списка не имеют одинаковое количество чисел.Если для достижения 4 миллионов в 1 списке требуется только 2 числа, а 7 чисел в совокупности достигают 7 миллионов, это нормально.

Пока оба суммированных списка равны 4 миллионам или выше.

Answer 1

Является ли эта определенная сумма достаточно низкой, чтобы ее можно было легко получить?Если да, то ваш алгоритм может быть таким простым: итерация i от 1 до количества элементов.Подведите первые цифры.если сумма больше, чем ваша определенная сумма (например, 4 миллиона), то вы закончили, иначе увеличьте значение i.

НО: если ваши определенные суммы высоки, и найти раздел не так просто, тогдау вас есть знаменитый Partition Probem (https://en.wikipedia.org/wiki/Partition_problem), это не так просто, но есть некоторые алгоритмы. Прочтите эту статью в Википедии или попробуйте Google "Решение проблем с разделами" или подобное.