我有一个类似于背包问题的问题，更具体地说是multidimensional variation。
我有一堆对象，它们都有一个成本，一个值和一个类别。我需要在最大成本下优化背包的值(value)，但每个类别中都有特定数量的对象。
我已经在C++中成功实现了原始的背包算法，而无需关注类别。
当我尝试添加类别时，我发现可以将其简单地视为多维背包问题，每个类别在新维度中的权重为0或1。
我的主要问题是，我不仅有一个最大值，例如:5个食物类型的对象，而且还有一个最小值，因为我需要和 5个食物类型的对象。
而且我不知道如何在算法中添加最小值。
显然，我可以使用一种一般情况，其中每个维度都有最大值和最小值，并针对总计进行优化，因为我的所有维度(除一个维度之外)都只有一个范围1，因此无论如何最终都会针对值(value)进行优化。此外，我可以将值的最小值设置为零，以避免一维没有最小值，并且仍然可以使用。
我正在使用C++，但老实说，即使是伪代码也可以，我只需要算法。
显然，如果可能，我还需要它与multidimensional variation一样快。
这是测试用例的示例。由于这主要是一个优化问题，因此实例很大，但是它可以在任何实例大小下工作。可能类别的数量和类别字段的数量是固定的。
您有一个最多可容纳100个重量单位的背包，以及1000个对象的列表，每个对象都有一个值，一个重量和一个类型。您特别需要带10个食物类型的物体，15个衣服类型的物体和5个工具。每个对象都有一个完全任意(但大于0)的美元值和权重单位。我将需要找到一种优化的配置，以确保最大重量和每种类型物品的具体数量。
对象列表将始终包含至少一个有效的配置，这意味着它将始终至少具有每种类型的足够的对象，这些对象最终将在最大权重范围内，因此我不必计划“无答案”案子。我只需要找到(可能)大量可用项目的最佳答案。
最佳答案
确切地知道每个类别可以选择多少个项目是一个很大的限制。考虑一个类别的最简单情况。您要精确选择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);
}
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
#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, }
关于c++ - 最小和最大的多维背包，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/43146315/
我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server
如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:
我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我
我需要用任何语言编写一个算法，根据3个因素对数组进行排序。我以度假村为例(如Hipmunk)。假设我想去度假。我想要最便宜的地方、最好的评论和最多的景点。但是，显然我找不到在所有3个中都排名第一的方法。Example(assumingthereare20importantattractions):ResortA:$150/night...98/100infavorablereviews...18of20attractionsResortB:$99/night...85/100infavorablereviews...12of20attractionsResortC:$120/night
因此，对于普通哈希，您可以使用它来获取key:hash.keys如何获取如下所示的多维哈希的第二维键:{""=>{"first_name"=>"test","last_name"=>"test_l","username"=>"test_user","title"=>"SalesManager","office"=>"test","email"=>"test@test.com"}}每个项目都是唯一的。所以我想从上面得到的键是:first_name,last_name,username,title,officeandemail 最佳答案
我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“
有没有办法让Ruby能够做这样的事情？classPlane@moved=0@x=0defx+=(v)#thisiserror@x+=v@moved+=1enddefto_s"moved#{@moved}times,currentxis#{@x}"endendplane=Plane.newplane.x+=5plane.x+=10putsplane.to_s#moved2times,currentxis15 最佳答案 您不能在Ruby中覆盖复合赋值运算符。任务在内部处理。您应该覆盖+，而不是+=。plane.a+=b与plane.a=
我正在尝试动态构建一个多维数组。我想要的基本上是这样的(为简单起见写出来):b=0test=[[]]test[b]这给了我错误:NoMethodError:undefinedmethod`test=[[],[],[]]而且它工作正常，但在我的实际使用中，我不会事先知道需要多少个数组。有一个更好的方法吗？谢谢 最佳答案 不需要像您正在使用的索引变量。只需将每个数组附加到您的test数组:irb>test=[]=>[]irb>test[["a","b","c"]]irb>test[["a","b","c"],["d","e","f"]]
出于某种原因，heroku尝试要求dm-sqlite-adapter，即使它应该在这里使用Postgres。请注意，这发生在我打开任何URL时-而不是在gitpush本身期间。我构建了一个默认的Facebook应用程序。gem文件:source:gemcuttergem"foreman"gem"sinatra"gem"mogli"gem"json"gem"httparty"gem"thin"gem"data_mapper"gem"heroku"group:productiondogem"pg"gem"dm-postgres-adapter"endgroup:development,:t
我是Ruby和这个网站的新手。下面两个函数是不同的，一个在函数外修改变量，一个不修改。defm1(x)x我想确保我理解正确-当调用m1时，对str的引用被复制并传递给将其视为x的函数。运算符当调用m2时，对str的引用被复制并传递给将其视为x的函数。运算符+创建一个新字符串，赋值x=x+"4"只是将x重定向到新字符串，而原始str变量保持不变。对吧？谢谢 最佳答案 String#+::str+other_str→new_strConcatenation—ReturnsanewStringcontainingother_strconc