在尽可能接近的情况下,将列表拆分为n个不同的匹配条件子列表

我已经使用动态编程为给定的问题制定了一个确定性解决方案,共享相同的代码 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) ^二 )如果你需要更多的解释,请告诉我。