c++ - 最小和最大的多维背包

Question

我有一个类似于背包问题的问题，更具体地说是multidimensional variation。

我有一堆对象，它们都有一个成本，一个值和一个类别。我需要在最大成本下优化背包的值(value)，但每个类别中都有特定数量的对象。

我已经在C++中成功实现了原始的背包算法，而无需关注类别。

当我尝试添加类别时，我发现可以将其简单地视为多维背包问题，每个类别在新维度中的权重为0或1。

我的主要问题是，我不仅有一个最大值，例如:5个食物类型的对象，而且还有一个最小值，因为我需要和 5个食物类型的对象。

而且我不知道如何在算法中添加最小值。

显然，我可以使用一种一般情况，其中每个维度都有最大值和最小值，并针对总计进行优化，因为我的所有维度(除一个维度之外)都只有一个范围1，因此无论如何最终都会针对值(value)进行优化。此外，我可以将值的最小值设置为零，以避免一维没有最小值，并且仍然可以使用。

我正在使用C++，但老实说，即使是伪代码也可以，我只需要算法。

显然，如果可能，我还需要它与multidimensional variation一样快。

这是测试用例的示例。由于这主要是一个优化问题，因此实例很大，但是它可以在任何实例大小下工作。可能类别的数量和类别字段的数量是固定的。

您有一个最多可容纳100个重量单位的背包，以及1000个对象的列表，每个对象都有一个值，一个重量和一个类型。您特别需要带10个食物类型的物体，15个衣服类型的物体和5个工具。每个对象都有一个完全任意(但大于0)的美元值和权重单位。我将需要找到一种优化的配置，以确保最大重量和每种类型物品的具体数量。

对象列表将始终包含至少一个有效的配置，这意味着它将始终至少具有每种类型的足够的对象，这些对象最终将在最大权重范围内，因此我不必计划“无答案”案子。我只需要找到(可能)大量可用项目的最佳答案。

Answer 1

确切地知道每个类别可以选择多少个项目是一个很大的限制。考虑一个类别的最简单情况。您要精确选择N个对象，以使值sum [v_i x_i]
Vanilla 背包问题

这是一个简短的演示:通过内存以标准0/1背包问题的解决方案为起点:

#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using uint = unsigned int;

template <typename T>
struct item {
    T value;
    uint weight;
};

template <typename T>
T knapSack(uint W, const std::vector< item<T> >& items) {

    std::map< std::pair<uint, uint>, T> cache;

    std::function<T(uint, uint)> recursion;
    recursion = [&] (uint n, uint w) {
        if (n == 0)
            return 0;
        auto it = cache.find(std::make_pair(n,w));
        if (it != cache.end())
            return it->second;
        T _v = items[n-1].value;
        uint _w = items[n-1].weight;
        T nextv;
        if (_w <= w)
            nextv = std::max(_v + recursion(n-1,w-_w),recursion(n-1,w));
        else
            nextv = recursion(n-1,w);
        cache.insert(std::make_pair(std::make_pair(n,w),nextv));
        return nextv;   
    };

    return recursion(items.size(),W);
}

我在这里的实现(使用递归lambda函数)强调了可读性而非最优性。选择索引
一类类别的背包问题，具有所需的固定对象数

我们可以继续添加新的限制，以跟踪所选元素的数量。为此，我们将注意到在每个递归步骤中新选择的对象比之前的对象多选择0或1个元素，就像权重总和相同或更大一样，即选择索引 N时，我们找不到索引 N的所有条目标记为最大值为0但无效:

template <typename T>
std::pair<T,bool> knapSackConstrained(uint W, uint K, const std::vector< item<T> >& items) {

    std::map< std::tuple<uint, uint, uint>, std::pair<T,bool> > cache;

    std::function<std::pair<T, bool>(uint, uint, uint)> recursion;
    recursion = [&] (uint n, uint w, uint k) {
        if (k > n)
            return std::make_pair(0,false);
        if (n == 0 || k == 0)
            return std::make_pair(0,true);
        auto it = cache.find(std::make_tuple(n,w,k));
        if (it != cache.end())
            return it->second;
        T _v = items[n-1].value;
        uint _w = items[n-1].weight;
        T nextv;
        bool nextvalid = true;
        if (_w <= w) {
            auto take = recursion(n-1,w-_w,k-1);
            auto reject = recursion(n-1,w,k);
            if (take.second and reject.second) {
                nextv = std::max(_v + take.first,reject.first);
            } else if (take.second) {
                nextv = _v + take.first;
            } else if (reject.second) {
                nextv = reject.first;
            } else {
                nextv = 0;
                nextvalid = false;
            }   
        } else {
            std::tie(nextv,nextvalid) = recursion(n-1,w,k);
        }
        std::pair<T,bool> p = std::make_pair(nextv,nextvalid);
        cache.insert(std::make_pair(std::make_tuple(n,w,k),p));
        return p;   
    };

    return recursion(items.size(),W,K);
}

这是运行此代码及其输出的简单主例程:

int main(int argc, char *argv[]) {
    std::vector< item<int> > items = {{60,10},{10,6},{10,6}};
    int  j = 13;
    std::cout << "Unconstrained: " << knapSack(j,items) << std::endl;
    for (uint k = 1; k <= items.size(); ++k) {
        auto p = knapSackConstrained(j,k,items);
        std::cout << "K = " << k << ": " << p.first;
        if (p.second)
            std::cout << std::endl;
        else
            std::cout << ", no valid solution" << std::endl;
    }
    return 0;
}

% OUTPUT %
Unconstrained: 60
K = 1: 60
K = 2: 20
K = 3: 0, no valid solution

由于这三个权重的总和已经大于阈值，因此不可能同时要求这三个权重。

具有固定类别的所需数量的多个类别的背包问题

上面仅部分解决了您的问题，因为您有多个类别，而不仅仅是一个类别。但是，我认为可以将其扩展为多维的，而无需太多额外的工作。确实，我怀疑以下代码对于多维情况(模错误)是正确的策略-它需要一些良好的测试用例进行验证。将单个参数K替换为类别编号的 vector ，并为项目struct提供一个类别字段。基本案例必须考虑每种可能的K> N案例(针对每个类别)，此外，必须扩展(i-1)st权重小于W的检查，以检查是否还需要至少1个项目第(i-1)个类别。

#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using uint = unsigned int;

template <typename T>
struct item {
    T value;
    uint weight;
    uint category;
};

template <typename T>
std::pair<T,bool> knapSack(uint W, const std::vector<uint>& K, const std::vector< item<T> >& items) {

    std::map< std::tuple<uint, uint, std::vector<uint> >, std::pair<T,bool> > cache;

    std::function<std::pair<T, bool>(uint, uint, std::vector<uint>)> recursion;
    recursion = [&] (uint n, uint w, std::vector<uint> k) {

        auto it = cache.find(std::make_tuple(n,w,k));
        if (it != cache.end())
            return it->second;

        std::vector<uint> ccount(K.size(),0);
        for (uint c = 0; c < K.size(); ++c) {
            for (uint i = 0; i < n; ++i) {
                if (items[i].category == c)
                    ++ccount[c];
            }
        }
        for (uint c = 0; c < k.size(); ++c) {
            if (k[c] > ccount[c]) {
                auto p = std::make_pair(0,false);
                cache.insert(std::make_pair(std::make_tuple(n,w,k),p));
                return p;
            }
        }

        uint sumk = 0; for (const auto& _k : k) sumk += _k;
        if (n == 0 || sumk == 0) {
            auto p = std::make_pair(0,true);
            cache.insert(std::make_pair(std::make_tuple(n,w,k),p));
            return p;
        }

        T _v = items[n-1].value;
        uint _w = items[n-1].weight;
        uint _c = items[n-1].category;
        T nextv;
        bool nextvalid = true;
        if (_w <= w and k[_c] > 0) {
            std::vector<uint> subk = k;
            --subk[_c];
            auto take = recursion(n-1,w-_w,subk);
            auto reject = recursion(n-1,w,k);
            if (take.second and reject.second) {
                nextv = std::max(_v + take.first,reject.first);
            } else if (take.second) {
                nextv = _v + take.first;
            } else if (reject.second) {
                nextv = reject.first;
            } else {
                nextv = 0;
                nextvalid = false;
            }   
        } else {
            std::tie(nextv,nextvalid) = recursion(n-1,w,k);
        }
        std::pair<T,bool> p = std::make_pair(nextv,nextvalid);
        cache.insert(std::make_pair(std::make_tuple(n,w,k),p));
        return p;   
    };

    return recursion(items.size(),W,K);
}

int main(int argc, char *argv[]) {
    std::vector< item<int> > items = {{60,10,0}, {100,20,1}, {120,30,0}, {140,35,1}, {145,40,0}, {180,45,1}, {160,50,1}, {170,55,0}};
    int  j = 145;
    for (uint k1 = 0; k1 <= items.size(); ++k1) {
        for (uint k2 = 0; k2 <= items.size(); ++k2) {
            auto p = knapSack(j,std::vector<uint>({k1,k2}),items);
            if (p.second)
                std::cout << "K0 = " << k1 << ", K1 = " << k2 << ": " << p.first << std::endl;
        }
    }
    return 0;
}

% OUTPUT (with comments) %

K0 = 0, K1 = 0: 0
K0 = 0, K1 = 1: 180 // e.g. {} from 0, {180} from 1
K0 = 0, K1 = 2: 340 // e.g. {} from 0, {160,180} from 1
K0 = 0, K1 = 3: 480 // e.g. {} from 0, {140,160,180} from 1
K0 = 1, K1 = 0: 170 // e.g. {170} from 0, {} from 1
K0 = 1, K1 = 1: 350 // e.g. {170} from 0, {180} from 1
K0 = 1, K1 = 2: 490 // e.g. {170} from 0, {140, 180} from 1
K0 = 1, K1 = 3: 565 // e.g. {145} from 0, {100, 140, 180} from 1
K0 = 2, K1 = 0: 315 // e.g. {145,170} from 0, {} from 1
K0 = 2, K1 = 1: 495 // e.g. {145,170} from 0, {180} from 1
K0 = 2, K1 = 2: 550 // e.g. {60,170} from 0, {140,180} from 1
K0 = 2, K1 = 3: 600 // e.g. {60,120} from 0, {100,140,180} from 1
K0 = 3, K1 = 0: 435 // e.g. {120,145,170} from 0, {} from 1
K0 = 3, K1 = 1: 535 // e.g. {120,145,170} from 0, {100} from 1
K0 = 3, K1 = 2: 605 // e.g. {60,120,145} from 0, {100,180} from 1
K0 = 4, K1 = 0: 495 // e.g. {60,120,145,170} from 0, {} from 1

对于给定的具有两个类别的项目集，输出似乎是正确的，尽管我的手动检查可能无法发现一些问题[此答案的早期版本确实存在一些错误]。所有未打印的案例都是没有解决方案的案例。

返回选定对象的集合

如果您希望函数返回所选对象的集合，则原则上这没有障碍-代码变得更加困惑。人类最容易理解的事情就是将 std::set<std::size_t>添加到 recursion和 knapSack返回的对象的元组中，并存储在缓存中，代表所选对象的索引集合。每次添加新对象时，都可以增加该对象集。产生的代码涉及大量整数集的复制，并且可能远非最优-更好的解决方案可能涉及静态 bool vector ，其条目可打开和关闭。但是，它有效并且有意义，所以这里是:

#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>

using uint = unsigned int;

template <typename T>
struct item {
    T value;
    uint weight;
    uint category;
};

template <typename T>
std::tuple<T,bool,std::set<size_t> > knapSack(uint W, std::vector<uint> K, const std::vector< item<T> >& items) {

    std::map< std::tuple<uint, uint, std::vector<uint> >, std::tuple<T,bool,std::set<std::size_t> > > cache;

    std::function<std::tuple<T,bool,std::set<std::size_t> >(uint, uint, std::vector<uint>&)> recursion;

    recursion = [&] (uint n, uint w, std::vector<uint>& k) {

        auto it = cache.find(std::make_tuple(n,w,k));
        if (it != cache.end())
            return it->second;

        std::vector<uint> ccount(K.size(),0);
        for (uint i = 0; i < n; ++i) {
            ++ccount[items[i].category];
        }

        for (uint c = 0; c < k.size(); ++c) {
            if (k[c] > ccount[c]) {
                auto p = std::make_tuple(0,false,std::set<std::size_t>{});
                cache.insert(std::make_pair(std::make_tuple(n,w,k),p));
                return p;
            }
        }
        uint sumk = 0; for (const auto& _k : k) sumk += _k;
        if (n == 0 || sumk == 0) {
            auto p = std::make_tuple(0,true,std::set<std::size_t>{});
            cache.insert(std::make_pair(std::make_tuple(n,w,k),p));
            return p;
        }

        T _v = items[n-1].value;
        uint _w = items[n-1].weight;
        uint _c = items[n-1].category;
        T nextv;
        bool nextvalid = true;
        std::set<std::size_t> nextset;
        if (_w <= w and k[_c] > 0) {
            --k[_c];
            auto take = recursion(n-1,w-_w,k);
            ++k[_c];
            auto reject = recursion(n-1,w,k);
            T a = _v + std::get<0>(take);
            T b = std::get<0>(reject);
            if (std::get<1>(take) and std::get<1>(reject)) {
                nextv = std::max(a,b);
                if (a > b) {
                    nextset = std::get<2>(take);
                    nextset.insert(n-1);
                } else {
                    nextset = std::get<2>(reject);
                }
            } else if (std::get<1>(take)) {
                nextv = a;
                nextset = std::get<2>(take);
                nextset.insert(n-1);
            } else if (std::get<1>(reject)) {
                nextv = b;
                nextset = std::get<2>(reject);
            } else {
                nextv = 0;
                nextvalid = false;
                nextset = {};
            }   
        } else {
            std::tie(nextv,nextvalid,nextset) = recursion(n-1,w,k);
        }
        auto p = std::make_tuple(nextv,nextvalid,nextset);
        cache.insert(std::make_pair(std::make_tuple(n,w,k),p));
        return p;   
    };

    return recursion(items.size(),W,K);
}

int main(int argc, char *argv[]) {
    std::vector< item<int> > items = {{60,10,0}, {100,20,1}, {120,30,0}, {140,35,1}, {145,40,0}, {180,45,1}, {160,50,1}, {170,55,0}};
    int  j = 145;
    for (uint k1 = 0; k1 <= items.size(); ++k1) {
        for (uint k2 = 0; k2 <= items.size(); ++k2) {
            auto p = knapSack(j,std::vector<uint>({k1,k2}),items);
            if (std::get<1>(p)) {
                std::cout << "K0 = " << k1 << ", K1 = " << k2 << ": " << std::get<0>(p);
                std::cout << "; contents are {";
                for (const auto& index : std::get<2>(p))
                    std::cout << index << ", ";
                std::cout << "}" << std::endl;
            }
        }
    }
    return 0;
}

这个的输出是

K0 = 0, K1 = 0: 0; contents are {}
K0 = 0, K1 = 1: 180; contents are {5, }
K0 = 0, K1 = 2: 340; contents are {5, 6, }
K0 = 0, K1 = 3: 480; contents are {3, 5, 6, }
K0 = 1, K1 = 0: 170; contents are {7, }
K0 = 1, K1 = 1: 350; contents are {5, 7, }
K0 = 1, K1 = 2: 490; contents are {3, 5, 7, }
K0 = 1, K1 = 3: 565; contents are {1, 3, 4, 5, }
K0 = 2, K1 = 0: 315; contents are {4, 7, }
K0 = 2, K1 = 1: 495; contents are {4, 5, 7, }
K0 = 2, K1 = 2: 550; contents are {0, 3, 5, 7, }
K0 = 2, K1 = 3: 600; contents are {0, 1, 2, 3, 5, }
K0 = 3, K1 = 0: 435; contents are {2, 4, 7, }
K0 = 3, K1 = 1: 535; contents are {1, 2, 4, 7, }
K0 = 3, K1 = 2: 605; contents are {0, 1, 2, 4, 5, }
K0 = 4, K1 = 0: 495; contents are {0, 2, 4, 7, }

算法复杂度

这不是我的专长，但我相信运行时复杂度是伪多项式，因为该算法与标准背包算法非常相似。