多维背包问题中的最小值和最大值

Question

我有一个问题，它与背包问题类似，更具体地说是多维变化。

我有一堆物品，每个物品都有成本、价值和类别。我需要在最大成本下对价值进行背包优化，但也需要每个类别中特定数量的物品。

我已经成功地在C++中实现了原始的背包算法，没有注意到类别。

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

我的主要问题不仅是有一个最大值，例如:5个食品类型的物品，还有一个最小值，因为我需要确切地 5个食品类型的物品。

我无法想出如何将最小值添加到算法中。

显然，我可以使用一个通用情况，其中每个维度都有一个最大值和最小值，并且优化总和，因为除了一个维度之外的所有维度只有1个范围，所以这将最终优化价值。此外，我可以将价值的最小值设置为零，以避免一个维度没有最小值，这仍然可以工作。

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

显然，如果可能的话，我也需要它快速，尽可能快地多维变化。

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

你有一个最大可以容纳100个单位重量的背包，以及一个由1000个物品组成的列表，每个物品都有一个价值、一个重量和一个类型。你需要准备恰好10种食品、15件衣服和5种工具。每个物品都有一个任意（但大于0）的美元价值和一个单位的重量。我需要找到最佳配置，以便在尊重最大重量和每种物品数量的情况下获得最大价值。

物品列表将始终包含至少一个有效的配置，这意味着它将始终至少具有足够的每种类型的物品，以使其不超过最大重量，因此我不必考虑“无答案”情况。我只需为可能巨大的可用物品找到最佳答案。

- Kaito Kid

---

请问您能否给出输入数据的大致大小估计？例如有多少个类别，每个类别中有多少条目等。 - Mann

我的原始解决方案有一个错误（if else的顺序应该颠倒），我已经重新发布了一个（更）正确的解决方案。 - jwimberley

@Mann 输入可能非常巨大，因为这主要是一个优化问题。另一方面，只有一个类别字段，而且该字段中只有三个类别。例如：背包重量容量为1000，有10万个物品，它们可以是食品、服装或工具，每个物品的重量在1-15之间，价值在1-25之间。我需要恰好30件工具、30件衣服和50件食品，并获得最高可能的价值。 - Kaito Kid

Answer 1

了解每一类别可以选择的物品数量非常重要。考虑最简单的情况，只有一个类别。您需要选择正好 N 个对象，以最大化 sum[v_i x_i] 的值，其中 sum[w_i x_i] < W，其中 x_i 等于 0 或 1（按照维基百科的符号表示）。新的约束条件是 sum[x_i] = N。这个约束条件可以通过在动态编程中添加另一个维度来包含在问题中，但需要明确检查解决方案是否有效并且确切地具有所需元素数量。

经典背包问题

下面是一个简要演示：从记忆化方法中使用以下解决方案作为标准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函数）强调可读性而非优化性。选择指数<N且重量总和<W的对象选择可以是选择指数<N-1且重量总和<W的对象或者是第N-1个对象与指数<N-1且重量总和<W-w[N-1]的对象一起选择。

具有固定所需物品数量的背包问题

我们可以增加一个新限制条件来跟踪所选元素的数量。我们会注意到，在每个递归步骤中新的对象选择都比之前多0个或1个元素，以相同或更大的重量总和的方式--即，选择指数<N且重量总和<W的K个对象可以是选择指数<N-1且重量总和<W的K个对象或对象N-1与指数<N-1且重量总和<W-w[N-1]的K-1个对象一起选择。然而，我们还希望跟踪违规情况--例如，当K>N时，我们无法找到具有指数<N的K个对象。在这种情况下，我们应报告最大可能值为0，因为选择是不可能的，但我们应将其标记为“无效”，以区别于递归的微不足道的基本情况。此外，任何试图将其用作子解的上层解决方案也应标记为无效。出于这个原因，我们将返回类型从简单值改为一个值和布尔对。作为基本情况的一部分，我们将所有K>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

由于3个权重的总和已经大于阈值，需要所有三个权重的解决方案是不可能的。

具有固定所需对象数量的多类背包问题

上面只部分解决了您的问题，因为您有多个类别而不仅仅是一个。但是，我相信可以在不太多的额外工作的情况下将其扩展为多维。事实上，除了一些错误检查，我怀疑以下代码是多维情况的正确策略 - 它需要一些良好的测试用例进行验证。单个参数K被替换为类别编号的向量，并且项目结构体获得类别字段。基本情况必须考虑每个可能的K> N情况（对于每个类别），并且除了检查（i-1）号重量小于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 添加到由递归和knapSack返回的对象元组中，并存储在缓存中，表示所选对象的索引集合。每次添加新对象时，可以增加此集合。生成的代码涉及大量整数集的复制，并且可能远非最佳 - 更好的解决方案可能涉及静态布尔向量，其条目被切换开和关。但是，它有效并且有意义，因此在这里介绍它：

#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, }

算法复杂度

虽然这不是我的专业领域，但我认为运行时间复杂度是伪多项式的，因为该算法与标准背包算法非常相似。

- jwimberley

---

这个答案看起来非常有前途和完整。我会在明天测试它是否有效后接受并颁发悬赏。非常感谢你的努力。 - Kaito Kid

@KaitoKid 不用谢！如果你的测试发现任何问题，请告诉我。 - jwimberley

你的代码复杂度是多少，我很好奇？ - Kaito Kid

@KaitoKid 关于你的第二条评论 - 是的，两者都可以；and是C++中惯用的表达方式，与&&完全相同（也许使用较少，但我更喜欢它），而我在我的代码中定义了using uint = unsigned int;。 - jwimberley

它非常好用（我在特定需要的一些东西上进行了一些修改，这与此处提出的问题无关）。给你，非常感谢！ - Kaito Kid

Answer 2

我实际上没有直接回答你的问题，无论是伪代码还是特定语言中算法的实际实现，但我可以在这里给你提供一份参考列表，我认为这些与该主题相关，可能会帮助你开发出一个可行的算法：

• 高性能异构计算
• 遗传学和人口分析：更好的块划分和连接策略用于个体单倍型分型
• 多块大小搜索算法用于快速块运动估计
• 并行计算：体系结构、算法和应用
• 一种在区间上进行数据最优划分的算法
• 并行划分再探
• 近似、随机化和组合优化。算法和技术
• 用于分形图像压缩的最佳分层划分
• 多级存储器层次结构中的高效树布局
• 选择适用于系统发育基因组数据集的最佳分区方案

虽然这些问题可能并不完全是背包算法问题，但我认为这些主题在某种程度上与您的算法整体成就有关。我认为这些会很有用，因为首先，背包问题本身就是分区算法的一种变体，具有许多实现和方案。此外，使用并行编程和多线程编程也可以帮助处理大型数据集。我找到了这些书籍和白皮书，我认为它们会很有价值。

基本上，你有一个背包K，它有一个容量KV，需要将其细分为小容量{KV1，KV2，... KVn}，这些小容量可以容纳不同的数据类型，每种类型都有一个价值、重量和类别或分类，而物品的重量表示它消耗的体积部分。你还有限制条件，即有一个[min，max]边界，其中限制是你必须至少拥有每个类别或分类中的一个。然后，在这些参数作为基本情景的基础上，你想要最大化KV，以尽可能多地包含元素，但希望尽可能高效地完成，需要花费最少的时间，并且希望避免二次和/或指数级别的时间和空间复杂度，而是采用线性到多项式级别的时间和空间复杂度。

查看其他独特不同的算法，例如分区算法、人口密度和增长、图像压缩等，可以让你深入了解你的具体问题，因为这些算法的总体基础和注意事项在本质上是相似的。

- Francis Cugler