我写了一个背包类,我用它来解决背包算法。这个类正在使用动态规划算法来解决这个问题。
我在代码中实现了一些优化,因此我使用线性O(W)空间来找到最大值,但当我试图找到见证时,我仍然需要O(nW)空间来保持布尔表。
有人能告诉我,是否有可能找到背包容量最大、空间较小、复杂度与O(nW)相同的证据,这里W是背包容量。
如果您认为代码中可能还有更多优化,请也告诉他们。
class Knapsack{
private:
vector< int > value, weight, answer, DP;
vector< bool > isin;
int capacity;
public:
Knapsack( vector< int > value, vector< int > weight, int capacity, bool needWitness ){
this->value = value;
this->weight = weight;
this->capacity = capacity;
this->answer.clear(); this->isin.clear(); this->DP.clear();
this->DP.resize( capacity + 1, false );
if ( needWitness ){
this->isin.resize( value.size() * (capacity + 1), false );
solveWithWitness();
}
else{
solveWithoutWitness();
}
}
void solveWithoutWitness(){
for ( int i = 0; i < value.size(); i++ ){
for ( int w = capacity; w >= weight[i]; w-- ){
if ( DP[w] < value[i] + DP[w - weight[i]] ){
DP[w] = value[i] + DP[w - weight[i]];
}
}
}
}
void solveWithWitness(){
for ( int i = 0; i < value.size(); i++ ){
for ( int w = capacity; w >= weight[i]; w-- ){
if ( DP[w] < value[i] + DP[w - weight[i]] ){
DP[w] = value[i] + DP[w - weight[i]];
isin[ i*capacity + w ] = true;
}
}
}
int position = value.size()-1;
int w = capacity;
while ( position >= 0 ){
if ( isin[ position*capacity + w ] ){
answer.push_back( position );
w -= weight[position];
}
position--;
}
}
vector< int > getWitness(){
return this->answer;
}
int solution(){
return DP[capacity];
}
};
你到处都在使用O,所以我可以给你一个有点复杂和尴尬的理论解决方案,它仍然满足你想要的时间限制:
运行无见证DP,共2步;这将告诉您仅使用前n/2项就可以达到W权重中的哪一个。现在,为剩余的n/2步骤运行DP,跟踪前n/2项到达每个单元格所需的重量。
如果您天真地以递归的方式应用此过程,则会得到类似于T(n,W)的时间重复
但我们计算出了前n/2个项目需要多少重量。我们只需要关心DP数组的前w个条目。因此,前半部分递归应该花费T(n/2,w)时间,后半部分递归应该花费T(n/2,w-w)时间,而到达那里所需的工作需要O(nW)时间。
T(n, W)形式的重复解
我对这个问题有点困惑。作为算法帮助我找到最大的利润从袋。但是这个算法并没有告诉我我应该拿哪一个项目会让我的利润最大。例如 n=4项,背包的容量M=8,利润=[15,10,9,5],重量分别为w=[1,5,3,4],当我解决这个问题时,我得到最大的利润为29 这里是解决方案[http://www.mafy.lut.fi/study/DiscreteOpt/DYNKNAP.pdf] 但是我想知道我应该
我正在为即将到来的测试复习,想知道是否有人能重述问题的b部分。这是从分发的复习表中得到的文本,但我不确定b部分到底在问什么。我更直截了当地猜测“生成一个不到0/1背包问题最优值1%的解”是什么意思。 b)[10pts]举了一个有两个对象的例子,说明对分数背包问题使用的相同的贪婪方法(略加修改,如果贪婪方法选择的最后一个对象不适合,则忽略它)得到的解不到0/1背包问题最优解的1%。
本文向大家介绍C中的0-1背包问题?,包括了C中的0-1背包问题?的使用技巧和注意事项,需要的朋友参考一下 背包是袋子。背包问题是根据物品的值将物品放入袋中的。目的是使袋子内的值最大化。在0-1背包中,您既可以放置物品也可以将其丢弃,没有将物品的某些部分放入背包的概念。 样本问题 重量分布 最大值为65,因此我们将项目2和3放入背包。 0-1背包问题计划 输出结果
在我为0/1背包和无界背包签出的所有DP解决方案中,解决方案方法总是这样定义的: 0/1背包:取第n项或不取第n项,使总价值最大化。例如,0/1背包 无界背包:将第n个物品视为最后挑选的物品,或(n-1)个物品视为最后挑选的物品,使总价值最大化。例如,无界背包 但无界背包也可以使用0/1背包的逻辑来解决,只需稍加调整。我的意思是,对于0/1背包,我们执行以下操作(使用第一个链接中的代码): 请注意
我目前正在研究一个路由问题(找到一个我想去的地方的子集[每个地方有一定的分数],同时不超过最大的旅行时间),并提出了1/0背包问题的变体,似乎解决了我最初的问题。 根据维基百科,1/0背包被描述为: 给定一组物品,每个物品都有质量和价值,确定集合中每个物品的数量,以便总重量小于或等于给定的限制,总价值尽可能大。 因此,对于每个项目,都有一个固定的重量(质量),当试图解决问题时,可以很容易地使用它,
我有这样的数据集: 长度:233333450560650780限制:5400 现在我的问题是,从设定的最高长度到最低长度中选择项目,以弥补限制或尽可能接近。 我知道背包和最小硬币兑换都能解决我的问题。我想知道哪个更好。 请注意,硬币变化是使用贪婪算法,背包使用动态编程