具有最小值和最大值的多维背包
Multidimensional Knapsack with minimum and maximum
我有一个类似于背包问题的问题，更具体地说是 multidimensional variation。
我有一堆对象，它们都有成本、价值和类别。我需要在最大成本下对 Knapsack 进行价值优化，但每个类别中也有特定数量的对象。
我在C++中成功实现了原始的背包算法，没有关注类别。
当我尝试添加类别时，我发现我可以简单地将其视为多维背包问题，每个类别在新维度中的权重为 0 或 1。
我的主要问题是我不仅有最大值，例如：5 个食物类型的对象，而且还有最小值，因为我需要 正好 5 个食物类型的对象.
而且我不知道如何在算法中添加最小值。
显然，我可以使用一般情况，其中每个维度都有最大值和最小值，并针对总计进行优化，因为除了一个维度之外，我的所有维度的范围都为 1，所以无论如何这最终都会针对价值进行优化.此外，我可以将值的最小值设置为零，以避免一维没有最小值，它仍然有效。
我正在使用 C++，但老实说，即使是伪代码也可以，我只需要算法。
显然我还需要它快，如果可能的话，尽可能快 multidimensional variation。
这里是测试用例的例子。由于这主要是一个优化问题，实例很大，但它应该适用于任何实例大小。可能的类别数和类别字段数是固定的。
您有一个最多可容纳 100 个重量单位的背包，以及一个包含 1000 个对象的列表，每个对象都有一个值、一个重量和一个类型。您特别需要携带 10 件食物类物品、15 件衣物类物品和 5 件工具。每个对象都有完全任意（但大于 0）的美元价值和单位重量。我需要根据每种物品的最大重量和具体数量找到价值的最佳配置。
对象列表将始终包含至少一个有效配置，这意味着它始终至少具有足够的每种类型的对象，这些对象将最终达到最大权重，因此我不必计划"no answer" 案例。我只需要为（可能）大量可用项目找到最佳答案。
确切地知道可以从每个类别中选择多少项目是一个很大的限制。考虑有一个类别的最简单的情况。您可以选择恰好 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 处的对象与 K-1 个索引 < N-1 的对象并且权重总和 < W - w[N-1]。但是，我们还想跟踪违规情况——例如，当 K>N 时，我们找不到索引 < N 的 K 个对象。在这种情况下，我们应该报告最大可能值为 0，因为选择是不可能的，但我们应该将其标记为 "invalid" 以将其与递归的普通基本情况区分开来。此外，链上任何试图将其用作子解决方案的解决方案也应标记为无效。为此，我们将 return 类型从一个简单的值更改为一对值和布尔值。作为基本情况的一部分，我们将所有 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
对于一组具有两个类别的给定项目，输出似乎是正确的，尽管我的手动检查可能未能发现一些问题 [此答案的早期版本确实存在一些错误]。所有未打印的案例都是没有解决方案的案例。
返回所选对象的集合
如果您希望该函数 return 选定对象的集合，原则上这不是障碍 - 代码只会变得更混乱。最容易理解的事情就是简单地向由 recursion 和 knapSack 编辑的对象 return 的元组添加一个 std::set<std::size_t>，并存储在缓存中，代表所选对象的索引集合。每次添加新对象时，都可以扩充该集合。生成的代码涉及大量整数集的复制，并且可能远非最佳 - 更好的解决方案可能涉及一个静态布尔向量，其条目被打开和关闭。但是，它有效且有意义，所以这里是：
#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, }
算法复杂度
这不是我的强项，但我相信运行时复杂度是伪多项式，因为该算法与标准背包算法非常相似。
我实际上并没有直接回答你的问题，要么是伪代码，要么是特定语言的算法的实际实现，但我在这里能做的是给你一个我认为相关的参考列表转到可能有助于指导您开发工作算法的主题：
- High Performance Heterogeneous Computing
- 遗传学和种群分析：更好的个体块分割和连接策略
单倍型分析
- Multiple block-size search algorithm for fast block motion estimation
- Parallel Computing: Architectures, Algorithms, and Applications
- 一种最优分割算法
区间数据
- Parallel Partition Revisited
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- OPTIMAL HIERARCHICAL PARTITIONS FOR FRACTAL IMAGE COMPRESSION
- Efficient Tree Layout in a Multilevel Memory Hierarchy
- Selecting optimal partitioning schemes for phylogenomic datasets
尽管其中许多可能不完全是背包算法问题；我认为这些主题可能以某种方式相关，以帮助您实现算法的整体成就。我认为这些将是有用的，因为首先背包问题本身就是具有许多实现和方案的分区算法的变体。此外，并行编程和多线程编程的使用也可能有助于处理大型数据集。我找到了一些我认为会很不错的书籍和白皮书。
基本上你有一个背包 K，它有一个体积 KV，需要细分成更小的体积 {KV1, KV2, ... KVn}，其中包含不同的数据类型，每种类型都有一个 value、weight 和 category or classification 以及项目的 weight 代表它消耗的体积部分。您还具有 [min, max] 边界的约束，并且您必须至少拥有每个 category 或 classification 中的一个。然后将这些参数作为您的基本场景，然后您希望最大化 KV 以包含尽可能多的 elements 但希望尽可能高效地完成它，希望花费最少的时间 linear to polynomial - time and space complexity 避免 quadratic and/or exponential - time and space complexities.
查看其他截然不同的算法，例如分区算法、人口密度和增长、图像压缩等，可以让您深入了解您的具体问题，因为这些算法的总体基础和注意事项在本质上是相似的。
我有一个类似于背包问题的问题，更具体地说是 multidimensional variation。
我有一堆对象，它们都有成本、价值和类别。我需要在最大成本下对 Knapsack 进行价值优化，但每个类别中也有特定数量的对象。
我在C++中成功实现了原始的背包算法，没有关注类别。
当我尝试添加类别时，我发现我可以简单地将其视为多维背包问题，每个类别在新维度中的权重为 0 或 1。
我的主要问题是我不仅有最大值，例如：5 个食物类型的对象，而且还有最小值，因为我需要 正好 5 个食物类型的对象.
而且我不知道如何在算法中添加最小值。
显然，我可以使用一般情况，其中每个维度都有最大值和最小值，并针对总计进行优化，因为除了一个维度之外，我的所有维度的范围都为 1，所以无论如何这最终都会针对价值进行优化.此外，我可以将值的最小值设置为零，以避免一维没有最小值，它仍然有效。
我正在使用 C++，但老实说，即使是伪代码也可以，我只需要算法。
显然我还需要它快，如果可能的话，尽可能快 multidimensional variation。
这里是测试用例的例子。由于这主要是一个优化问题，实例很大，但它应该适用于任何实例大小。可能的类别数和类别字段数是固定的。
您有一个最多可容纳 100 个重量单位的背包，以及一个包含 1000 个对象的列表，每个对象都有一个值、一个重量和一个类型。您特别需要携带 10 件食物类物品、15 件衣物类物品和 5 件工具。每个对象都有完全任意（但大于 0）的美元价值和单位重量。我需要根据每种物品的最大重量和具体数量找到价值的最佳配置。
对象列表将始终包含至少一个有效配置，这意味着它始终至少具有足够的每种类型的对象，这些对象将最终达到最大权重，因此我不必计划"no answer" 案例。我只需要为（可能）大量可用项目找到最佳答案。
确切地知道可以从每个类别中选择多少项目是一个很大的限制。考虑有一个类别的最简单的情况。您可以选择恰好 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 处的对象与 K-1 个索引 < N-1 的对象并且权重总和 < W - w[N-1]。但是，我们还想跟踪违规情况——例如，当 K>N 时，我们找不到索引 < N 的 K 个对象。在这种情况下，我们应该报告最大可能值为 0，因为选择是不可能的，但我们应该将其标记为 "invalid" 以将其与递归的普通基本情况区分开来。此外，链上任何试图将其用作子解决方案的解决方案也应标记为无效。为此，我们将 return 类型从一个简单的值更改为一对值和布尔值。作为基本情况的一部分，我们将所有 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
对于一组具有两个类别的给定项目，输出似乎是正确的，尽管我的手动检查可能未能发现一些问题 [此答案的早期版本确实存在一些错误]。所有未打印的案例都是没有解决方案的案例。
返回所选对象的集合
如果您希望该函数 return 选定对象的集合，原则上这不是障碍 - 代码只会变得更混乱。最容易理解的事情就是简单地向由 recursion 和 knapSack 编辑的对象 return 的元组添加一个 std::set<std::size_t>，并存储在缓存中，代表所选对象的索引集合。每次添加新对象时，都可以扩充该集合。生成的代码涉及大量整数集的复制，并且可能远非最佳 - 更好的解决方案可能涉及一个静态布尔向量，其条目被打开和关闭。但是，它有效且有意义，所以这里是：
#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, }
算法复杂度
这不是我的强项，但我相信运行时复杂度是伪多项式，因为该算法与标准背包算法非常相似。
我实际上并没有直接回答你的问题，要么是伪代码，要么是特定语言的算法的实际实现，但我在这里能做的是给你一个我认为相关的参考列表转到可能有助于指导您开发工作算法的主题：
- High Performance Heterogeneous Computing
- 遗传学和种群分析：更好的个体块分割和连接策略 单倍型分析
- Multiple block-size search algorithm for fast block motion estimation
- Parallel Computing: Architectures, Algorithms, and Applications
- 一种最优分割算法 区间数据
- Parallel Partition Revisited
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- OPTIMAL HIERARCHICAL PARTITIONS FOR FRACTAL IMAGE COMPRESSION
- Efficient Tree Layout in a Multilevel Memory Hierarchy
- Selecting optimal partitioning schemes for phylogenomic datasets
尽管其中许多可能不完全是背包算法问题；我认为这些主题可能以某种方式相关，以帮助您实现算法的整体成就。我认为这些将是有用的，因为首先背包问题本身就是具有许多实现和方案的分区算法的变体。此外，并行编程和多线程编程的使用也可能有助于处理大型数据集。我找到了一些我认为会很不错的书籍和白皮书。
基本上你有一个背包 K，它有一个体积 KV，需要细分成更小的体积 {KV1, KV2, ... KVn}，其中包含不同的数据类型，每种类型都有一个 value、weight 和 category or classification 以及项目的 weight 代表它消耗的体积部分。您还具有 [min, max] 边界的约束，并且您必须至少拥有每个 category 或 classification 中的一个。然后将这些参数作为您的基本场景，然后您希望最大化 KV 以包含尽可能多的 elements 但希望尽可能高效地完成它，希望花费最少的时间 linear to polynomial - time and space complexity 避免 quadratic and/or exponential - time and space complexities.
查看其他截然不同的算法，例如分区算法、人口密度和增长、图像压缩等，可以让您深入了解您的具体问题，因为这些算法的总体基础和注意事项在本质上是相似的。