将列表拆分为 n 个不同的子列表匹配条件，同时保持尽可能接近

Question

我的问题与这个问题有很多共同点：

主要区别在于我有一个稍微不同的指标来确定哪个拆分 "best"，并且在这样做时我有一个任意条件要遵守。

我列表中的每一项都有两个组成部分。重量和体积。我必须将它们分成 n 个不同的子组，同时让每个子组的总权重尽可能接近。测试的方法很简单，就是找出最重和最轻子组之间的差异。这个差异越小越好。这意味着子组 [15][15][15][10] 与子组 [15][13][11][10].

的最终得分相同

然后，这是我无法弄清楚如何添加到建议的算法中作为链接问题的答案的部分，我有一个必须遵守的硬条件。每个子组都有一个最大音量 [v]，其中 none 个可以超过它。超过以上不会降低分数，它会使整个答案无效。

如何调整用作前一个答案的算法（和代码片段）以考虑体积条件和略有不同的评分方法？

我正在寻找关于如何做到这一点的代码、伪代码或书面（详细）解释。这个问题被标记为 C#，因为这就是我正在使用的，但我相信我可以从任何非深奥的语言翻译，所以如果你用代码回答，请随意使用你喜欢的任何东西。

正如在另一个问题中提到的，这个问题非常复杂，找到最佳解决方案在合理的计算时间内可能不可行，因此我正在寻找给出的答案"good enough" 解决方案，即使它可能不是最好的。

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)²) 如果您需要更多解释，请告诉我 ^^;

将列表拆分为 n 个不同的子列表匹配条件，同时保持尽可能接近

Split a list into n different sublists matching condition while remaining as close as possible

c#

algorithm

optimization

partitioning