Разбить список на n различных подсписков, соответствующих условию, оставаясь как можно ближе

Question

Мой вопрос имеет много общего с этим: Разделите список чисел на n блоков, чтобы они имели (близко к) равные суммы и сохраняли первоначальный порядок

Основное различие заключается в том, что у меня есть немного другая метрика, чтобы определить, какое разделение является «наилучшим», и при этом у меня есть произвольное условие, которое нужно соблюдать.

Каждый элемент в моем списке имеет два компонента.Вес и Объем.Я должен разделить их на n различных подгрупп, при этом суммарные веса каждой подгруппы должны быть как можно ближе.Способ проверить это просто получить разницу между самой тяжелой и самой легкой подгруппой.Чем меньше эта разница, тем лучше.Это означает, что подгруппы [15] [15] [15] [10] стоят в конечном счете столько же, сколько и подгруппы [15] [13] [11] [10].

Тогда это частьЯ не могу понять, как добавить в алгоритмы, предложенные в качестве ответов на связанный вопрос, у меня сложное условие, которое нужно соблюдать.Существует максимальный объем [v] для каждой подгруппы, и ни один из них не может превышать ее.Упомянутое выше не снижает оценку, оно делает недействительным весь ответ.

Как алгоритмы (и фрагменты кода), используемые в качестве ответов на предыдущий, могут быть адаптированы для учета условия громкости и немного отличающихсяметод оценки?

Я ищу код, псевдокод или письменное (подробное) объяснение того, как это можно сделать.Вопрос с тэгом C #, потому что это то, что я использую, но я уверен, что я могу переводить с любого неэзотерического языка, так что не стесняйтесь переходить к тому, что вам нравится, если вы отвечаете с кодом.

Как уже упоминалосьв другом вопросе эта проблема очень сложна, и нахождение лучшего решения может оказаться невозможным за разумное время вычислений, поэтому я ищу ответ, который дает «достаточно хорошее» решение, даже если оно можетне будь лучшим.

Answer 1

Я сформулировал детерминистическое решение для данной проблемы, используя динамическое программирование, разделяя код для того же самого https://ideone.com/pkfyxg

#include<iostream>
#include<vector>
#include<climits>
#include<cstring>
#include<algorithm>
using namespace std;

// Basic structure for the given problem
struct Item {
    float weight;
    float volume;

    Item(float weight, float volume) {
        this->weight = weight;
        this->volume = volume;
    }

    bool operator<(const Item &other) const {
        if(weight == other.weight) {
            return volume < other.volume;
        }
        return weight < other.weight;
    }
};

// Some constant values
const static int INF = INT_MAX / 100;
const static int MAX_NUM_OF_ITEMS = 1000;
const static int MAX_N = 1000;

// Parameters that we define in main()
float MAX_VOLUME;
vector<Item> items;

// DP lookup tables
int till[MAX_NUM_OF_ITEMS];
float dp[MAX_NUM_OF_ITEMS][MAX_N];

/**
 * curIndex: the starting index from where we aim to formulate a new group
 * left: number of groups still left to be formed
 */ 
float solve(int curIndex, int left) {
    // Baseline condition
    if(curIndex >= items.size() && left == 0) {
        return 0;
    }
    if(curIndex >= items.size() && left != 0) {
        return INF;
    }
    // If we have no more groups to be found, but there still are items left
    // then invalidate the solution by returning INF
    if(left <= 0 && curIndex < items.size()) {
        return INF;
    }

    // Our lookup dp table
    if(dp[curIndex][left] >= 0) {
        return dp[curIndex][left];
    }

    // minVal is the metric to optimize which is the `sum of the differences
    // for each group` we intialize it as INF
    float minVal = INF;

    // The volume of the items we're going to pick for this group
    float curVolume = 0;

    // Let's try to see how large can this group be by trying to expand it 
    // one item at a time
    for(int i = curIndex; i < items.size(); i++) {
        // Verfiy we can put the item i in this group or not
        if(curVolume + items[i].volume > MAX_VOLUME) {
            break;
        }
        curVolume += items[i].volume;
        // Okay, let's see if it's possible for this group to exist
        float val = (items[i].weight - items[curIndex].weight) + solve(i + 1, left - 1);
        if(minVal >= val) {
            minVal = val;
            // The lookup table till tells that the group starting at index
            // curIndex, expands till i, i.e. [curIndex, i] is our valid group
            till[curIndex] = i + 1;
        }
    }
    // Store the result in dp for memoization and return the value
    return dp[curIndex][left] = minVal;
}

int main() {
    // The maximum value for Volume
    MAX_VOLUME = 6;
    // The number of groups we need
    int NUM_OF_GROUPS = 5;

    items = vector<Item>({
    // Item(weight, volume)
        Item(5, 2),
        Item(2, 1),
        Item(10, 3),
        Item(7, 2),
        Item(3, 1),
        Item(5, 3),
        Item(4, 3),
        Item(3, 2),
        Item(10, 1),
        Item(11, 3),
        Item(19, 1),
        Item(21, 2)
    });

    // Initialize the dp with -1 as default value for unexplored states
    memset(dp, -1, sizeof dp);

    // Sort the items based on weights first
    sort(items.begin(), items.end());

    // Solve for the given problem
    int val = solve(0, NUM_OF_GROUPS);

    // If return value is INF, it means we couldn't distribute it in n
    // groups due to the contraint on volume or maybe the number of groups
    // was greater than the number of items we had ^_^
    if(val >= INF) {
        cout << "Not possible to distribute in " << NUM_OF_GROUPS;
        return 0;
    }

    // If a solution exists, use the lookup till array to find which items
    // belong to which set  
    int curIndex = 0, group = 1;
    while(curIndex < items.size()) {
        cout << "Group #" << group << ": ";
        for(int i = curIndex; i < till[curIndex]; i++)
            cout << "(" << items[i].weight << ", " << items[i].volume << ") ";
        cout << '\n';
        group++;    
        curIndex = till[curIndex];
    }
}

Я добавил комментарии к коду, чтобы помочь вам понять егоработает лучше.Общая сложность во время выполнения для этого же O (num_of_groups * (num_of_items) ² ) Дайте мне знать, если вам нужно больше объяснений по поводу того же ^^;